題目描述
給定一個 NN 個點，MM 條有向邊的帶非負(fù)權(quán)圖，請你計算從 SS 出發(fā)，到每個點的距離。

數(shù)據(jù)保證你能從 SS 出發(fā)到任意點。

輸入格式
第一行為三個正整數(shù) N, M, SN,M,S。 第二行起 MM 行，每行三個非負(fù)整數(shù) u_i, v_i, w_iu
i
? ,v
i
? ,w
i
? ，表示從 u_iu
i
? 到 v_iv
i
? 有一條權(quán)值為 w_iw
i
? 的邊。

輸出格式
輸出一行 NN 個空格分隔的非負(fù)整數(shù)，表示 SS 到每個點的距離。

輸入輸出樣例
輸入 #1 復(fù)制
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
輸出 #1 復(fù)制
0 2 4 3
說明/提示
樣例解釋請參考 數(shù)據(jù)隨機(jī)的模板題。

1 \leq N \leq 1000001≤N≤100000；

1 \leq M \leq 2000001≤M≤200000；

S = 1S=1；

1 \leq u_i, v_i\leq N1≤u
i
? ,v
i
? ≤N；

0 \leq w_i \leq 10 ^ 90≤w
i
? ≤10
9
,

0 \leq \sum w_i \leq 10 ^ 90≤∑w
i
? ≤10
9
。

本題數(shù)據(jù)可能會持續(xù)更新，但不會重測，望周知。

2018.09.04 數(shù)據(jù)更新 from @zzq

鏈?zhǔn)角跋蛐堑哪０?#xff0c;可以過本題。第二個代碼是vector建圖的模板，不卡常的情況下很好使。

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <map> #include <set> #include <vector> #define rep(i,x,n) for(int i=x;i<n;i++) #define repd(i,x,n) for(int i=x;i<=n;i++) #define pii pair<int,int> #define pll pair<long long ,long long> #define gbtb std::ios::sync_with_stdio(false) #define MS0(X) memset((X), 0, sizeof((X))) #define MSC0(X) memset((X), '\0', sizeof((X))) #define pb push_back #define mp make_pair #define fi first #define se second #define gg(x) getInt(&x) using namespace std; typedef long long ll; inline void getInt(int* p); /*** TEMPLATE CODE STARTS HERE ***/ const int maxn=100010; const int MAXM=200000; // const int INF= 0x3f3f3f3f;struct Edge {int to,next;ll dist;Edge(){}Edge(int tt,ll dd){to=tt;dist=dd;}bool operator < (const Edge x ) const{return dist > x.dist;} }edge[MAXM]; int head[maxn],tot; void addedge(int u,int v,ll c) {edge[tot].to = v;edge[tot].next = head[u];edge[tot].dist=c;head[u] = tot++; } priority_queue<Edge> heap; ll dis[maxn]; int t,n,star; bool vis[maxn]; void dijkstra (int strat) {// memset(dis,INF,sizeof(dis));repd(i,1,n){dis[i]=1e18;vis[i]=0;}dis[strat]=0;heap.push(Edge(strat,dis[strat]));while(!heap.empty()){Edge x= heap.top();heap.pop();int u=x.to;if(vis[u]){continue;}vis[u]=1;for(int i = head[u];i != -1;i = edge[i].next){Edge now = edge[i];if(dis[now.to]>x.dist+now.dist){dis[now.to]=x.dist+now.dist;heap.push(Edge(now.to,dis[now.to]));}}}} int main() {scanf("%d %d %d",&n,&t,&star);int a,b,d;memset(head,-1,sizeof(head));repd(i,1,t){scanf("%d %d %d",&a,&b,&d);addedge(a,b,d);}dijkstra(star);repd(i,1,n){printf("%lld ",dis[i]);}return 0; }inline void getInt(int* p) {char ch;do {ch = getchar();} while (ch == ' ' || ch == '\n');if (ch == '-') {*p = -(getchar() - '0');while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 - ch + '0';}}else {*p = ch - '0';while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 + ch - '0';}} }

``` cpp

轉(zhuǎn)載于:https://www.cnblogs.com/qieqiemin/p/11296156.html

總結(jié)

以上是生活随笔為你收集整理的l洛谷P4779 【模板】单源最短路径（标准版）（dijkstra）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。