题解 P3371 【【模板】单源最短路径（弱化版）】
0AND1STORY
2018-11-05 20:44:40
简单的Dijkstra模板题
废话不多说，直接上代码：
```cpp
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#define maxn 10010
#define inf 0x7f
#define intinf 0x7f7f7f7f
using namespace std;
struct edge{
int to,w,next;
};
int n,m,s,es = 1;
int head[maxn];
int dis[maxn];
int vis[maxn];
edge E[500010];
void E_add(int u,int v,int w){
E[es].to = v;
E[es].w = w;
E[es].next = head[u];
head[u] = es ++;
}
void init(){
memset(head,-1,sizeof(head));
memset(dis,inf,sizeof(dis));
scanf("%d%d%d",&n,&m,&s);
for(int i = 0;i < m;i ++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
E_add(u,v,w);
}
}
void dijkstra(){
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
dis[s] = 0;
q.push(make_pair(dis[s],s));
while(!q.empty()){
int u = q.top().second;
q.pop();
if(vis[u]){
continue;
}
vis[u] = 1;
for(int i = head[u];i != -1;i = E[i].next){
int v = E[i].to;
if(dis[v] > dis[u]+E[i].w){
dis[v] = dis[u]+E[i].w;
q.push(make_pair(dis[v],v));
}
}
}
for(int i = 1;i <= n;i ++){
if(dis[i] == intinf){
printf("2147483647 ");
continue;
}
printf("%d ",dis[i]);
}
printf("\n");
}
int main(){
init();
dijkstra();
return 0;
}
```