Descripton The kingdom of Hellcife has several cities that are connected by some roads. One day, the king of Hellcife, Bair Jolsonaro, decided to set fire on some of these cities, just for fun. It’s known that the i-th city has a number Ti, indicating that if the fire reaches that city at time X, then at time X+Ti this city will be completely burnt. After a city is completely burnt, the fire begins to spread across all the roads that are connected to this city, with speed of one meter per second.
Your task is simple: you have to find, for each city, the amount of time it takes for the city to be completely burnt, knowing that at time 0 the king Bair Jolsonaro set fire on some cities.
Input The first line of input contains three numbers N, M and K (1≤N,M,K≤105), indicating the number of cities in Hellcife, the number of roads in Hellcife, and the number of cities Bair Jolsonaro initially set fire, respectively.
Each of the following M lines contains three integers Ai, Bi, and Ci (1≤Ai,Bi≤N, Ai≠Bi, 1≤Ci≤105), indicating that there is a road between cities Ai and Bi with length of Ci meters.
The next line of input contains N numbers Ti (1≤i≤N, 1≤Ti≤105).
The last line of the input contains K numbers Xi (1≤i≤K, 1≤Xi≤N), indicating that the Xi-th city was chosen by Bair Jolsonaro to be set on fire in the beginning.
Output The output consists of N lines, the i-th of them indicates the amount of time it takes for the i-th city to be completely burnt.
Examples
Input 5 5 1 1 2 1 2 3 4 3 4 5 4 5 10 1 5 13 1 2 3 4 5 1
Output 1 4 11 20 19
Solution 多源最短路，一开始把多个起点都压入队列再用dijkstra求解
Code
#include <bits/stdc++.h> using namespace std; const int MX = 2e5 + 7; int n,m,k; int ecnt,head[MX<<1]; struct Edge{ int v,w,next; }e[MX << 1]; struct node{ int now; ll w; inline bool operator<(const node&x)const{ return w > x.w; } }; void add(int u,int v,int w){ e[++ecnt].v = v; e[ecnt].w = w; e[ecnt].next = head[u]; head[u] = ecnt; } int t[MX]; bool st[MX]; ll dis[MX]; void dijkstra(){ priority_queue<node>q; bool vis[MX]; for(int i = 1;i <= n;++i){ vis[i] = false; if(!st[i]) dis[i] = LINF; else q.push((node){i,1ll * t[i]}), dis[i] = t[i]; } while(!q.empty()){ node tmp = q.top();q.pop(); int u = tmp.now; if(vis[u]) continue; vis[u] = true; for(int i = head[u];i;i = e[i].next){ int v = e[i].v; ll w = e[i].w; if(dis[v] >= dis[u] + w + t[v]){ dis[v] = dis[u] + w + t[v]; q.push((node){v,dis[v]}); } } } } int main(){ scanf("%d %d %d",&n,&m,&k); for(int i = 1;i <= m;++i){ int u,v,w;scanf("%d %d %d",&u,&v,&w); add(u,v,w);add(v,u,w); } for(int i = 1;i <= n;++i){ scanf("%d",&t[i]); } for(int i = 1;i <= k;++i){ int x;scanf("%d",&x);st[x] = true; } dijkstra(); for(int i = 1;i <= n;++i) printf("%lld\n", dis[i]); }