题目链接

最短路——【模板】单源最短路径（弱化版）（dijkstra）

题目描述

如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

输入格式

第一行包含三个整数 n,m,s，分别表示点的个数、有向边的个数、出发点的编号。

接下来 m 行每行包含三个整数 u,v,w，表示一条 u→v 的，长度为 w 的边。

输出格式

输出一行 n 个整数，第 i 个表示 s 到第 i 个点的最短路径，若不能到达则输出 2³¹-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; }