首先可以知道，对于在哪个时候攻占一个城市，应该是他的最短到达时间和最早进入时间的最大值（max(d1[i], d2[i])）。
最短到达时间：就是朴素的最短路d1[i]。
最早进入时间：设所有到达有他的结界发生器的城市为j，那么应该是在所有最短时间中取max，作为d2[i]。
于是就可以用dijkstra写了。
每一次成功更新节点 i 的d1时，就更新所有 i 能控制的节点 j 的d2。
我们还要记录每一个节点的入度，代表控制它的城市有几个，然后如果他的d2被更新了一次，就减1，若果为0，就代表所有控制他的城市都已经处理完了，于是就可以吧这个城市加入优先队列中，参与dijkstra。
最后的答案就是 max(d1[n], d2[n])。
1 #include<cstdio>
2 #include<iostream>
3 #include<algorithm>
4 #include<cmath>
5 #include<cstring>
6 #include<cstdlib>
7 #include<vector>
8 #include<queue>
9 #include<stack>
10 #include<cctype>
11 using namespace std;
12 #define enter puts("")
13 #define space putchar(' ')
14 #define Mem(a) memset(a, 0, sizeof(a))
15 typedef long long ll;
16 typedef double db;
17 const int INF = 0x3f3f3f3f;
18 const db eps = 1e-8;
19 const int maxn = 3e3 + 5;
20 inline ll read()
21 {
22 ll ans = 0;
23 char ch = getchar(), last = ' ';
24 while(!isdigit(ch)) last = ch, ch = getchar();
25 while(isdigit(ch)) ans = (ans << 3) + (ans << 1) + ch - '0', ch = getchar();
26 if(last == '-') ans = -ans;
27 return ans;
28 }
29 inline void write(ll x)
30 {
31 if(x < 0) putchar('-'), x = -x;
32 if(x >= 10) write(x / 10);
33 putchar(x % 10 + '0');
34 }
35
36 int n, m;
37 vector<int> v[maxn],c[maxn], su[maxn]; //su[i]代表有哪些城市控制城市i
38 int cnt[maxn]; //记录入度
39
40 #define pr pair<int, int>
41 #define mp make_pair
42 int d1[maxn], d2[maxn];
43 bool in[maxn];
44 void dijkstra(int s)
45 {
46 for(int i = 1; i <= n; ++i) d1[i] = INF;
47 d1[s] = 0;
48 priority_queue<pr, vector<pr>, greater<pr> > q;
49 q.push(mp(d1[s], s));
50 while(!q.empty())
51 {
52 pr node = q.top(); q.pop();
53 int now = node.second, dis = node.first;
54 if(in[now]) continue;
55 in[now] = 1;
56 for(int i = 0; i < (int)v[now].size(); ++i)
57 {
58 if(dis + c[now][i] < d1[v[now][i]])
59 {
60 d1[v[now][i]] = dis + c[now][i];
61 if(!cnt[v[now][i]]) q.push(mp(max(d1[v[now][i]], d2[v[now][i]]), v[now][i]));
62 //只有入度为0的节点才可以被加入队列
63 }
64 }
65 for(int i = 0; i < (int)su[now].size(); ++i)
66 {
67 cnt[su[now][i]]--;
68 // d2[su[now][i]] = max(d2[su[now][i]], dis);
69 if(!cnt[su[now][i]])
70 {
71 d2[su[now][i]] = dis;
72 // 这句话和68句话是等价的，因为最后一个到达控制它的城市时间一定是最长的
73 q.push(mp(max(d1[su[now][i]], d2[su[now][i]]), su[now][i]));
74 }
75 }
76 }
77 write(max(d1[n], d2[n]));
78 }
79
80 int main()
81 {
82 n = read(); m = read();
83 for(int i = 1; i <= m; ++i)
84 {
85 int x = read(), y = read(), w = read();
86 v[x].push_back(y); c[x].push_back(w);
87 }
88 for(int i = 1; i <= n; ++i)
89 {
90 cnt[i] = read();
91 for(int j = 1; j <= cnt[i]; ++j) su[read()].push_back(i);
92 }
93 dijkstra(1);
94 return 0;
95 }
View Code