UESTC1639云中谁寄锦书来？雁字回时，月满西楼

题目链接&＃xff1a;http://acm.uestc.edu.cn/#/problem/show/1639

题意&＃xff1a;
在n个点m条边的无向图上&＃xff0c;有k个出口
从起点出发&＃xff0c;每到一个点&＃xff08;包括起点&＃xff09;&＃xff0c;该点连出的边中有d条会被封锁
求最坏情况下到达出口的最短路
数据范围&＃xff1a;
1<&＃61;n<&＃61;100000
1<&＃61;m<&＃61;1000000

题解&＃xff1a;

Dijkstra拓展
由于求最坏情况下的最短路&＃xff0c;对于每个点&＃xff0c;显然最优的前d条边不能走。
对于边u->v&＃xff0c;必然要先得到v到出口的最坏情况下的最短路才能得到u经过该边再到出口的最坏情况下的最短路&＃xff0c;

也就是该边对于u的价值&＃xff0c;所以要从出口往回考虑。
令f[i]表示i到出口的最坏情况下的最短路&＃xff0c;同dijkstra算法一样&＃xff0c;每个点i可以分为f[i]已确定的和f[i]未确定的
初始时自然是对于每个出口x&＃xff0c;f[x]&＃61;0已确定。
对于f[v]已确定的点v&＃xff0c;将边权为w的边u->v以f[v]&＃43;w为关键字加入小根堆中。
对于每个点i还要记录cnt[i]&＃61;k&＃xff0c;表示到i后&＃xff0c;i连出的最优的前k条边已被封锁。
每次取出堆顶对应的边u->v&＃xff08;若f[u]已确定直接弹出&＃xff09;则该边为u连出的&＃xff08;除已被封锁的边外&＃xff09;最优的边
若cnt[u]

//UESTC 1639#include
using namespace std;
const int maxn &＃61; 1e5&＃43;7;
const int maxm &＃61; 1e6&＃43;7;
const int inf &＃61; 0x3f3f3f3f;
vector int,int> > G[maxn];
int dis[maxn], vis[maxn], cnt[maxn];
priority_queue int,int>, vectorint, int> > , greaterint, int> > >pq;
int u, v, w, k, d, n, m, len;
void Dij()
{memset(vis, 0, sizeof(vis));while(!pq.empty()){u &＃61; pq.top().second;w &＃61; pq.top().first;pq.pop();if(vis[u]) continue;if(cnt[u] &＃61;&＃61; d){dis[u] &＃61; w;vis[u] &＃61; 1;}else{cnt[u]&＃43;&＃43;;continue;}for(int i &＃61; 0; i <(int)G[u].size(); i&＃43;&＃43;){v &＃61; G[u][i].second;len &＃61; G[u][i].first;if(dis[v] > len &＃43; w){pq.push(make_pair(len&＃43;w, v));}}}
}
int main()
{while(~scanf("%d %d %d %d", &n,&m,&k,&d)){while(!pq.empty()) pq.pop();for(int i&＃61;0; i<&＃61;n; i&＃43;&＃43;) dis[i]&＃61;inf;memset(cnt, 0, sizeof(cnt));for(int i&＃61;0; ifor(int i&＃61;1; i<&＃61;m; i&＃43;&＃43;){scanf("%d %d %d", &u,&v,&w);G[u].push_back(make_pair(w, v));G[v].push_back(make_pair(w, u));}while(k--){scanf("%d", &u);cnt[u] &＃61; d;dis[u] &＃61; 0;pq.push(make_pair(0, u));}Dij();if(dis[0]&＃61;&＃61;inf) dis[0]&＃61;-1;printf("%d\n", dis[0]);}return 0;
}