题目链接

最短路——【模板】单源最短路径（标准版）（dijkstra）

题目描述

给定一个 n 个点，m 条有向边的带非负权图，请你计算从 s 出发，到每个点的距离。

数据保证你能从 s 出发到任意点。

输入格式

第一行为三个正整数 n,m,s。第二行起 m 行，每行三个非负整数 u_i,v_i,w_i，表示从 u_i 到 v_i 有一条权值为 w_i 的有向边。

输出格式

输出一行 n 个空格分隔的非负整数，表示 s 到每个点的距离。

输入输出样例

输入

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; }