#1093 : 最短路徑·三：SPFA算法
時間限制:10000ms
單點時限:1000ms
內存限制:256MB
描述
萬圣節的晚上，小Hi和小Ho在吃過晚飯之后，來到了一個巨大的鬼屋！

鬼屋中一共有N個地點，分別編號為1…N，這N個地點之間互相有一些道路連通，兩個地點之間可能有多條道路連通，但是并不存在一條兩端都是同一個地點的道路。

不過這個鬼屋雖然很大，但是其中的道路并不算多，所以小Hi還是希望能夠知道從入口到出口的最短距離是多少？

提示：Super Programming Festival Algorithm。
輸入
每個測試點（輸入文件）有且僅有一組測試數據。

在一組測試數據中：

第1行為4個整數N、M、S、T，分別表示鬼屋中地點的個數和道路的條數，入口（也是一個地點）的編號，出口（同樣也是一個地點）的編號。

接下來的M行，每行描述一條道路：其中的第i行為三個整數u_i, v_i, length_i，表明在編號為u_i的地點和編號為v_i的地點之間有一條長度為length_i的道路。

對于100%的數據，滿足N<=10^5，M<=106, 1 <= length_i <= 10^3, 1 <= S, T <= N, 且S不等于T。

對于100%的數據，滿足小Hi和小Ho總是有辦法從入口通過地圖上標注出來的道路到達出口。

輸出
對于每組測試數據，輸出一個整數Ans，表示那么小Hi和小Ho為了走出鬼屋至少要走的路程。

樣例輸入
5 10 3 5
1 2 997
2 3 505
3 4 118
4 5 54
3 5 480
3 4 796
5 2 794
2 5 146
5 4 604
2 5 63
樣例輸出
172
/*
這題點非常多，邊比較少，宜用spfa
由于n很大，直接用二維數組內存會超限，
所以需要用鄰接表

struct edge {int v;//可達點int w;//與可達點邊的長度edge(int e,int len):v(e),w(len){}//構造函數，初始化v,w }; vector<edge>a[MAXN];

*/
AC_code:

#include <stdio.h> #include <vector> #include <queue> #include <string.h> #include <algorithm> #define MAXN 100005 #define INF 0x3f3f3f3f using namespace std; int n,m,s,t,k; struct edge {int v;int w;edge(int e,int len):v(e),w(len){} }; vector<edge>a[MAXN]; int dis[MAXN]; bool vis[MAXN]; void SPFA() {queue<int>q;q.push(s);vis[s] = true;while(!q.empty()){k = q.front();q.pop();vis[k] = false;//！！！這里錯寫成了vis[s] = false ，找錯找了n久n久，Wrong到爆炸 int x,y;for(int i = 0; i < a[k].size(); i++){x = a[k][i].v;y = a[k][i].w;if(dis[x] > dis[k] + y){dis[x] = dis[k] + y;if(!vis[x]){q.push(x);vis[x] = true;}}}} } int main() {scanf("%d%d%d%d",&n,&m,&s,&t);int u,v,len;for(int i = 0; i < m; i++){scanf("%d%d%d",&u,&v,&len);a[u].push_back(edge(v,len));a[v].push_back(edge(u,len));//上面兩行code也可以寫成下面的形式/*edge e1(v,len),e2(u,len);a[u].push_back(e1);a[v].push_back(e2);*/}memset(dis,INF,sizeof(dis));dis[s] = 0;SPFA();printf("%d\n",dis[t]);return 0; }

總結

以上是生活随笔為你收集整理的#1093 : 最短路径·三：SPFA算法(邻接表)的全部內容，希望文章能夠幫你解決所遇到的問題。

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