題目背景

本題測試數據為隨機數據，在考試中可能會出現構造數據讓SPFA不通過，如有需要請移步?P4779。

題目描述

如題，給出一個有向圖，請輸出從某一點出發到所有點的最短路徑長度。

輸入格式

第一行包含三個整數N、M、S，分別表示點的個數、有向邊的個數、出發點的編號。

接下來M行每行包含三個整數Fi、Gi、Wi，分別表示第i條有向邊的出發點、目標點和長度。

輸出格式

一行，包含N個用空格分隔的整數，其中第i個整數表示從點S出發到點i的最短路徑長度（若S=i則最短路徑長度為0，若從點S無法到達點i，則最短路徑長度為2147483647）

輸入輸出樣例

輸入 #1復制 4 6 1 1 2 2 2 3 2 2 4 1 1 3 5 3 4 3 1 4 4 輸出 #1復制 0 2 4 3

說明/提示

時空限制：1000ms,128M

數據規模：

對于20%的數據：N<=5，M<=15；

對于40%的數據：N<=100，M<=10000；

對于70%的數據：N<=1000，M<=100000；

對于100%的數據：N<=10000，M<=500000。保證數據隨機。

對于真正 100% 的數據，請移步?P4779。請注意，該題與本題數據范圍略有不同。

樣例說明：

圖片1到3和1到4的文字位置調換

?

本題根據數據邊數m<=500000，鄰接矩陣存不下，只能使用靜態鄰接表存儲。

?

#include<cstdio> #include<queue> using namespace std;const long long inf=2147483647; const int maxn=10005; const int maxm=500005; using namespace std; int n,m,s,num_edge=0; int dis[maxn],vis[maxn],head[maxm]; struct Edge{int next,to,dis; }edge[maxm];void add(int from,int to,int dis){ edge[++num_edge].next=head[from]; edge[num_edge].to=to;edge[num_edge].dis=dis;head[from]=num_edge; }void spfa(){queue<int> q;for(int i=1; i<=n; i++) {dis[i]=inf;vis[i]=0;}q.push(s); dis[s]=0; vis[s]=1;while(!q.empty()){int u=q.front();q.pop(); vis[u]=0;for(int i=head[u];i;i=edge[i].next){int v=edge[i].to; if(dis[v]>dis[u]+edge[i].dis){dis[v]=dis[u]+edge[i].dis;if(vis[v]==0){vis[v]=1;q.push(v);}}}} }int main(){scanf("%d%d%d",&n,&m,&s);for(int i=1; i<=m; i++){int f,g,w;scanf("%d%d%d",&f,&g,&w); add(f,g,w);}spfa();for(int i=1;i<=n;i++){ if(s==i){printf("0 ");}else{printf("%d ",dis[i]);}}return 0; }

?

轉載于:https://www.cnblogs.com/hrj1/p/11160489.html

總結

以上是生活随笔為你收集整理的【模板】单源最短路径（弱化版）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。