题目描述

一张n个点m条边的图，通过每条边需要一定的时间。有一些限制条件，每个限制条件形如“x保护y”，表示到达y的最短时间不能小于到达x的最短时间（即如果在其之前到达，则需要等待至xd到达）。问1到n的最短时间。

输入

第一行两个正整数 N, M。 接下来 M行，每行三个正整数 ui, vi, wi，表示有一条从城市ui到城市 vi的单 向道路，自爆机器人通过这条道路需要 wi的时间。 之后 N 行，每行描述一个城市。首先是一个正整数 li，维持这个城市结界所 使用的结界发生器数目。之后li个1~N 之间的城市编号，表示每个结界发生器的 位置。如果 Li = 0，则说明该城市没有结界保护，保证L1 = 0 。

输出

仅包含一个正整数 ，击败杰森国所需的最短时间。

样例输入

6 6

1 2 1

1 4 3

2 3 1

2 5 2

4 6 2

5 3 2

0

0

0

1 3

0

2 3 5

样例输出

5

---

题解

堆优化Dijkstra

题意不能再简洁了。。。再简洁就一眼傻逼题了。。。

对于每个点，维护它的到达时间$f[i]$和所有保护点都到达的时间$g[i]$，那么当它到达并且所有保护点都到达时用$max(f[i],g[i])$来更新答案即可。

用堆优化Dijkstra实现，时间复杂度$O(m\log n)$

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;#define N 3010#define M 70010typedef long long ll;typedef pair
          
            pr;priority_queue
           
             q;vector
            
              p[N];int head[N] , to[M] , next[M] , cnt , c[N] , vis[N];ll len[M] , f[N] , g[N];inline void add(int x , int y , ll z){ to[++cnt] = y , len[cnt] = z , next[cnt] = head[x] , head[x] = cnt;}int main(){ int n , m , i , j , x , y; ll z; scanf("%d%d" , &n , &m); for(i = 1 ; i <= m ; i ++ ) scanf("%d%d%lld" , &x , &y , &z) , add(x , y , z); memset(f , 0x3f , sizeof(f)) , memset(g , 0x3f , sizeof(g)); for(i = 1 ; i <= n ; i ++ ) { scanf("%d" , &c[i]); for(j = 1 ; j <= c[i] ; j ++ ) scanf("%d" , &x) , p[x].push_back(i); if(!c[i]) g[i] = 0; } f[1] = 0 , q.push(pr(0 , 1)); while(!q.empty()) { z = -q.top().first , x = q.top().second , q.pop(); if(vis[x]) continue; vis[x] = 1; for(i = head[x] ; i ; i = next[i]) { if(f[to[i]] > z + len[i]) { f[to[i]] = z + len[i]; if(!c[to[i]]) q.push(pr(-max(f[to[i]] , g[to[i]]) , to[i])); } } for(i = 0 ; i < (int)p[x].size() ; i ++ ) { c[p[x][i]] -- ; if(!c[p[x][i]]) g[p[x][i]] = z , q.push(pr(-max(f[p[x][i]] , g[p[x][i]]) , p[x][i])); } } printf("%lld\n" , max(f[n] , g[n])); return 0;}