題目

一個有向圖，每個點有個默認方向和若干個其他方向，走默認方向權值為0，其他方向權值為1，求最短路

輸入

3 2 1(3個點，點2到點1)
2 2 3（2個點，起點為1，2為默認點，3為其他點）
2 3 1（2個點，起點為2，3為默認點，1為其他點）
2 1 2

輸出

0

---

解題思路

其實就像我題目說的那樣默認方向權值為0，其他方向權值為1，求最短路。這里用SPFA算法。

---

代碼

#include<cstdio> using namespace std; struct woc{int next,x,y,w; };//日常鄰接表 woc a[50001]; int xx,yy,n,m,k,state[10001],ls[10001],t,head,tail,f[10001],star,over; bool v[10001]; int main() {scanf("%d%d%d",&n,&star,&over);state[1]=1;int u=0; for (int i=1;i<=n;i++){scanf("%d",&xx);for (int j=1;j<=xx;j++){scanf("%d",&yy);if (j==1) a[++u].w=0;else a[++u].w=1;//判斷默認方向a[u].next=ls[i];ls[i]=u;a[u].x=i;a[u].y=yy;//鄰接表}} for (int i=1;i<=n;i++) f[i]=2147483647;head=0;tail=1;state[1]=star;v[state[1]]=true;f[star]=0;//初始化while (head!=tail){head++;//出隊head=(head-1)%n+1;//循環隊列t=ls[state[head]];//讀邊while (t!=0){if (f[a[t].x]+a[t].w<f[a[t].y]){f[a[t].y]=f[a[t].x]+a[t].w;//松弛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;//解封}if (f[over]==2147483647) printf("-1");//如果無解else printf("%d\n",f[over]); }

總結

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

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