題目

一個無向圖，求點1到每個點的最短路的路徑數量

輸入

5 7(5個點,7條邊)
1 2(表示1到2有邊)
1 3
2 4
3 4
2 3
4 5
4 5

輸出

（答案mod100003）
1
1
1
2
4

---

解題思路

注意這是無向圖，然后請看數據范圍

對于20%的數據，N ≤ 100；
對于60%的數據，N ≤ 1000；
對于100%的數據，N<=1000000，M<=2000000。

這是個稀疏圖，數據大，所以我們用SPFA法（其實bfs也可以過）。

---

代碼

#include<cstdio> using namespace std; struct woc{int next,x,y; };//鄰接表 woc a[2000001]; int xx,yy,n,m,k,state[1000001],ls[1000001],t,head,tail,f[1000001],s[1000001]; bool v[1000001]; int main() {scanf("%d%d",&n,&m);state[1]=1;int u=0;for (int i=1;i<=m;i++){scanf("%d%d",&xx,&yy);a[++u].next=ls[xx];a[u].x=xx;a[u].y=yy;ls[xx]=u;a[++u].next=ls[yy];a[u].x=yy;a[u].y=xx;ls[yy]=u;//無向圖}for (int i=1;i<=n;i++) f[i]=2147483647;//初始化head=0;tail=1;state[1]=1;v[state[1]]=true;f[1]=0; s[1]=1;//開始處理while (head!=tail){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];//繼承上一個點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;}}else if(f[a[t].x]+1==f[a[t].y]){s[a[t].y]=(s[a[t].y]+s[a[t].x])%100003;//計算點}t=a[t].next;//下一條邊}v[state[head]]=false;//解封}for (int i=1;i<=n;i++)printf("%d\n",s[i]);//輸出 }

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

*其實我看了題解*

轉載于:https://www.cnblogs.com/sslwyc/p/9218611.html

總結

以上是生活随笔為你收集整理的洛谷P1144-最短路计算【日常最短路,日常图论,SPFA】的全部內容，希望文章能夠幫你解決所遇到的問題。

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