【题目】

题目描述：

Picks 在 YXJ 城旅游。城中有 N 个景点，这些景点之间依靠路连接。

然而 YXJ 城水利工程做得非常差……一些景点处拥有路表的下水道口，随着雨水增加，下水道口会一起爆开。下水道口爆开之后，水便会沿着所有路流动。不同路的长度不同，所以不同路上水流过的时间不同。你可以认为水的流动互不影响，即一条路从两端同时流入水并独立流出是可行的。

现在，所有下水道口一起爆开了，YXJ 为了抢救他的城市，需要你提供每一个景点被水淹没的最早时间。

输入格式：

第一行三个数：N，M，K ，分别代表景点数、路径数、拥有下水道口的景点数。
第二行有 K 个数，每一个数表示该景点拥有一个下水道口。
接下来 M 行，每行三个数：u，v，w ，表示存在一条从 u 到 v 的双向路，水流过这条路需要 w 的时间。

输出格式：

输出一行 N 个数，分别表示该景点被水淹没的最早时间。
拥有下水道口的景点你可以认为淹没的最早时间为 0 。

样例数据：

输入

3 2 2
1 2
1 3 2
2 3 3

输出

0 0 2

备注：

【数据范围】
对于 20% 的数据：1 ≤ N, M ≤ 10
对于 40% 的数据：1 ≤ N, M ≤ 100
对于 60% 的数据：1 ≤ N, M ≤ 1000
对于 80% 的数据：1 ≤ N, M ≤ 10000
对于 100% 的数据：1 ≤ N, M ≤ 100000； 0 ≤ ti ≤ 1000；0＜w ≤ 1000 。

 

【分析】

emmm，很简单的一道最短路径的题

只有一个小小的技巧：在可以从多个起点出发的话，可以新建一个虚点向这些起点连一条权值为 0 的边，然后从这个虚点开始跑 dijkstra，这样做的好处是可以只跑一次 dijkstra，保证了时间复杂度

 

【代码】

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100005
#define M 300005
using namespace std;
int n,m,k,t;
int d[N],first[N];
int v[M],w[M],next[M];
priority_queue<pair<int,int> >q;
void add(int x,int y,int z)
{t++;next[t]=first[x];first[x]=t;v[t]=y;w[t]=z;
}
void dijkstra(int s)
{int x,y,i,j;memset(d,127,sizeof(d));d[s]=0;q.push(make_pair(0,s));while(!q.empty()){x=q.top().second;q.pop();for(i=first[x];i;i=next[i]){y=v[i];if(d[y]>d[x]+w[i]){d[y]=d[x]+w[i];q.push(make_pair(-d[y],y));}}}
}
int main()
{int x,y,z,i;scanf("%d%d%d",&n,&m,&k);for(i=1;i<=k;++i){scanf("%d",&x);add(0,x,0);}for(i=1;i<=m;++i){scanf("%d%d%d",&x,&y,&z);add(x,y,z);add(y,x,z);}dijkstra(0);for(i=1;i<=n;++i)printf("%d ",d[i]);return 0;
}