云中谁寄锦书来？雁字回时，月满西楼。
Time Limit: 6000/3000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)Submit Status
在干完 TheBigOne（一票大的）之后，劫犯们得准备逃跑路线了。
城市可以看作 n 个点 m 条边的无向图，节点编号为 0 到 n−1，其中有 k 个点为安全屋，劫犯们只要到达其中一个安全屋就能摆脱警察的追捕。
劫犯们从联合储蓄（节点 0）出发，希望能在最短的时间内到达安全屋。
但是警察对劫犯紧追不舍，每当劫犯到达一个节点，警察就立刻封锁与该点相连的边。
由于警力有限，对于当前点警察最多能够封锁与其相连的 d 条边。
现在劫犯想知道，在最坏情况下，他们能到达安全屋的最短时间。
Input
第一行四个整数 n 、m 、k 和 d，含义如上文所描述。接下来 m 行每行三个整数 u 、v 和 w，表示节点 u 和 v 之间有一条边，且通过该条边要花费 w 的时间。
接下来一行有 k 个整数，表示安全屋所在节点编号。
1≤n≤100000，1≤m≤1000000，0≤k≤n，0≤d≤m，0≤u 、v<n，0≤w≤10000 。
Output
若劫犯们不能到达安全屋，则输出 −1 。否则输出最坏情况下劫犯们到达安全屋的最短时间。
Sample input and output
Sample Input Sample Output
3 3 1 0 2
0 1 1
1 2 1
0 2 3
2
3 3 1 1 -1
0 1 1
1 2 1
0 2 3
2
Source
UESTC Training for Graph Theory
UESTC 1639 云中谁寄锦书来？雁字回时，月满西楼。
My Solution
题意：在n个点m条边的无向图上，有k个出口从起点出发，每到一个点（包括起点），
该点连出的边中有d条会被封锁，求最坏情况下到达出口的最短路。
Dijkstra拓展
由于求最坏情况下的最短路，对于每个点，显然最优的前d条边不能走。
对于边u->v，必然要先得到v到出口的最坏情况下的最短路才能得到u经过该边再到出口的最坏情况下的最短路，
也就是该边对于u的价值，所以要从出口往回考虑。
令f[i]表示i到出口的最坏情况下的最短路，同dijkstra算法一样，每个点i可以分为f[i]已确定的和f[i]未确定的
初始时自然是对于每个出口x，f[x]=0已确定。
对于f[v]已确定的点v，将边权为w的边u->v以f[v]+w为关键字加入小根堆中。
对于每个点i还要记录cnt[i]=k，表示到i后，i连出的最优的前k条边已被封锁。
每次取出堆顶对应的边u->v（若f[u]已确定直接弹出）则该边为u连出的（除已被封锁的边外）最优的边
若cnt[u]<d，该边必然会被封锁，那么将cnt[u]加1，弹出堆顶
若cnt[u]=d，那么可以确定f[u]=f[v]+w，再用u更新连向u的边，弹出堆顶。
重复这一过程直到确定f[0]的值，该值即为答案。
时间复杂度 O(nlogn)
空间复杂度 O(n)
#include <iostream>#include <cstdio>#include <queue>#include <vector>#include <cstring>using namespace std;typedef long long LL;typedef pair<int, int> ii;const int MAXN = 1e5 + 8;const int MAXM = 1e6 + 8;const int INF = 2e9 + 8;vector<ii> sons[MAXN];int dis[MAXN];int cnt[MAXN];bool vis[MAXN];priority_queue<ii, vector<ii>, greater<ii> > pq;//O(nlogn)inline void ex_dijkstra(int n, int d){memset(vis, false, sizeof vis);int u, v, w, dist, sz, i;while(!pq.empty()){u = pq.top().second;dist = pq.top().first;pq.pop();if(vis[u]) continue;else{if(cnt[u] == d){dis[u] = dist;vis[u] = true;}else{cnt[u]++;continue;}}sz = sons[u].size();for(i = 0; i < sz; i++){v = sons[u][i].first;w = sons[u][i].second;if(dist + w < dis[v]){//dis[v] = d + w;pq.push(ii(dist + w, v));}}}}int main(){#ifdef LOCALfreopen("f.txt", "r", stdin);//freopen("f.out", "w", stdout);int T = 4;while(T--){#endif // LOCALios::sync_with_stdio(false); cin.tie(0);int n, m, k, d, i, u, v, w;//cin >> n;scanf("%d%d%d%d", &n, &m, &k, &d);for(i = 0; i < m; i++){scanf("%d%d%d", &u, &v, &w);sons[u].push_back(ii(v, (int)w));sons[v].push_back(ii(u, (int)w));}for(int i = 0; i <= n; i++){dis[i] = INF;}for(i = 0; i < k; i++){scanf("%d", &u);dis[u] = 0;cnt[u] = d;pq.push(ii(0, u));}ex_dijkstra(n, d);if(dis[0] == INF) puts("-1");else printf("%d\n", dis[0]);#ifdef LOCALwhile(!pq.empty()) pq.pop();memset(cnt, 0, sizeof cnt);for(i = 0; i <= n; i++) sons[i].clear();cout << endl;}#endif // LOCALreturn 0;}
Thank you!
------fromProLights
