最短路——【模板】单源最短路径(弱化版)(dijkstra)
程序员文章站
2024-01-14 16:39:28
...
最短路——【模板】单源最短路径(弱化版)(dijkstra)
题目描述
如题,给出一个有向图,请输出从某一点出发到所有点的最短路径长度。
输入格式
第一行包含三个整数 n,m,s,分别表示点的个数、有向边的个数、出发点的编号。
接下来 m 行每行包含三个整数 u,v,w,表示一条 u→v 的,长度为 w 的边。
输出格式
输出一行 n 个整数,第 i 个表示 s 到第 i 个点的最短路径,若不能到达则输出 231-1。
输入输出样例
输入
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
输出
0 2 4 3
#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
const int maxn=500005;
int n,m,s,u,v,w;
struct node{
int to,len;
};
vector<node> f[maxn];
long long dis[maxn];
int vis[maxn];
void dijkstra(int t)
{
priority_queue<pii,vector<pii>,greater<pii> > q;
dis[t]=0;
q.push(pii(0,t));
while(!q.empty()){
pii x=q.top();
q.pop();
int tt=x.second;
if(vis[tt]){
continue;
}
vis[tt]=1;
for(int i=0;i<f[tt].size();i++){
node a=f[tt][i];
if(dis[a.to]>dis[tt]+a.len){
dis[a.to]=dis[tt]+a.len;
q.push(pii(dis[a.to],a.to));
}
}
}
}
int main()
{
cin>>n>>m>>s;
for(int i=0;i<m;i++){
cin>>u>>v>>w;
f[u].push_back({v,w});
}
for(int i=1;i<=n;i++){
dis[i]=2147483647;
}
memset(vis,0,sizeof(vis));
dijkstra(s);
for(int i=1;i<=n;i++){
printf("%lld ",dis[i]);
}
return 0;
}