题目链接：

思路：题目意思很简单，就是说如果没有攻占保护x的城市，就不能攻占,我们可以用pro[x]记录保护x的所有城市被攻占的最早时间，那么能到x的最短时间为pro[x]和到达x的最短路中的较大者 .dij入队过程中只把In[x]（没有被包含的城市）入队 对于出队的x,它的最短时间已经确定,表示已经被占领,它所保护的城市的保护度减 1,一旦某个被保护的城市的保护度为零且已经到底（未占领，d[x]!=inf），就可以确定到达它的 最短时间（为max(pro[x],dist[x])）,它也就到了入队的时机。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 using namespace std; 8 typedef long long LL; 9 typedef pair
            
             Pair;10 #define inf (1ll)<<5511 #define MAXN 333312 13 struct Node {14 int v,w;15 };16 int In[MAXN];17 LL dist[MAXN],pro[MAXN];18 bool mark[MAXN];19 vector
             
              Map[MAXN];20 vector
              
               vet[MAXN];21 int n,m;22 23 void Dijkstra(){24 for(int i=1;i<=n;i++){ dist[i]=inf;pro[i]=0; }25 dist[1]=0;26 memset(mark,false,sizeof(mark));27 priority_queue
               
                
                 ,greater
                 
                   >Q;28 Q.push(make_pair(dist[1],1));29 while(!Q.empty()){30 Pair pp=Q.top();31 Q.pop();32 int u=pp.second;33 if(mark[u])continue;34 mark[u]=true;35 for(int i=0;i
                  
                   dist[u]+w){48 dist[v]=max(dist[u]+w,pro[v]);49 if(In[v]==0){ Q.push(make_pair(dist[v],v)); }50 }51 }52 }53 }54 55 56 int main() {57 int _case,u,v,w,x;58 scanf("%d",&_case);59 while(_case--) {60 scanf("%d%d",&n,&m);61 for(int i=1; i<=n; i++) {62 Map[i].clear();63 vet[i].clear();64 }65 while(m--) {66 scanf("%d%d%d",&u,&v,&w);67 Node p;68 p.v=v,p.w=w;69 Map[u].push_back(p);70 }71 for(int i=1; i<=n; i++) {72 scanf("%d",&In[i]);73 for(int j=1; j<=In[i]; j++) {74 scanf("%d",&x);75 vet[x].push_back(i);76 }77 }78 Dijkstra();79 printf("%I64d\n",dist[n]);80 }81 return 0;82 }