前言

這是一篇遲到的博客

---

題目

找一條最廉價的最短路徑

---

輸入輸出（建議無視）

Input

輸入文件第一行有兩個整數m和n，用一個空格隔開，其中，m是頂點數，而n是邊數。接下來的n行給出所有的邊及其價值，每行有3個整數(相鄰兩個整數間有一個空格)，表示起點，終點和邊的價值。頂點最多有100個，編號在0到99之間。邊最多有1000條，其價值在0到2^15-1之間。

Output

輸出文件僅有一行包含一個整數，即V0→V1的廉價最短路徑的費用。當出現有多個廉價最短路徑的情況時，它們的費用是一樣的。

Sample Input

4 5
0 2 2
0 3 2
0 1 10
2 1 2
3 1 2

Sample Output

10

---

解題思路

正常最短路算法，只不過加上一個判斷

---

代碼

#include<cstdio> using namespace std; struct woc{long long next,x,y,w; }; woc a[1001]; long long xx,yy,n,m,k,state[101],ls[101],t,head,tail,f[101],s[101]; bool v[101]; int main() {scanf("%lld%lld",&n,&m);state[1]=1;int u=0;for (int i=1;i<=m;i++){scanf("%lld%lld%lld",&xx,&yy,&a[u+1].w);xx++;yy++;a[++u].next=ls[xx];a[u].x=xx;a[u].y=yy;ls[xx]=u;}for (int i=1;i<=n;i++) {f[i]=2147483647;s[i]=2147483647;}head=0;tail=1;state[1]=1;v[state[1]]=true;f[1]=0; s[1]=0;while (head!=tail)//SPFA{head++;head=(head-1)%n+1;t=ls[state[head]];while (t!=0){if (f[a[t].x]+1<f[a[t].y] || s[a[t].y]>s[a[t].x]+a[t].w && f[a[t].x]+1==f[a[t].y]){s[a[t].y]=s[a[t].x]+a[t].w;//改變價值f[a[t].y]=f[a[t].x]+1;if (!v[a[t].y]){tail++;tail=(tail-1)%n+1;state[tail]=a[t].y;v[a[t].y]=true;}}t=a[t].next;}v[state[head]]=false;}printf("%lld",s[2]); } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的ssl2661-廉价最短路径【SPFA】的全部內容，希望文章能夠幫你解決所遇到的問題。

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