【UVA10806】Dijkstra, Dijkstra [spfa][最小費用流]

luogu連結：UVA10806 Dijkstra, Dijkstra.  

固定起點1和終點n，從1到n，再從n回到1，去和回的路上相同的邊隻能用一次，求兩次的和最短，如果去的時候不能去到終點或者回的時候回不到起點那麼就輸出Back to jail，否則輸出兩次和的最小值（此圖是無向圖，不會有重邊，邊的權值在大于1小于1000）

直接1到n一次最短路，n到1一次最短路，再求和  顯然是錯的QAQ  以下from 

正反的最短路可能有公共邊 而每條路隻能走一次

可能有兩次最短路，但是卻有共用邊，那麼去的時候肯定會用掉這條共用邊，因為回來的時候不能再用這條共用邊，那麼是不是應該完全放棄另一條沒有用過的最短路而另尋路徑呢？不是的，而是可以用一個最好的方法，就是消去那條共用邊的權（想想為什麼來時候的邊權要取反）

可以這樣了解，兩條最短路，都可以看成 前部分+共用邊+後部分 ， 這裡前部分和後部分都是獨立的，沒有共用的，那麼綜合兩次的走法，其實可以變為 最短路1的前部分+最短路2的後部分，為去的路徑，最短路2的後部分+最短路1的前部分，為回的路徑，這樣子，相當于交換了路徑，但是我們并不關心路徑，我們隻關心兩次和最小，這樣并不改變和，而且還消掉了共用邊的權，其實相當于兩次走都沒有進過共用邊

1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=100+5,inf=0x3f3f3f3f;
 4 int n,m,mp[N][N],fro[N];
 5 inline int rd()
 6 {
 7     int x=0,w=0;char ch=0;
 8     while(!isdigit(ch)) w|=ch=='-',ch=getchar();
 9     while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
10     return w?-x:x;
11 }
12 
13 int vis[N],dis[N];
14 void spfa(int x)
15 {
16     memset(vis,0,sizeof(vis));
17     memset(fro,1,sizeof(fro));
18     memset(dis,inf,sizeof(dis));
19     for(int i=1;i<=n;i++) dis[i]=inf;
20     deque<int> q;
21     q.push_back(x);vis[x]=1,dis[x]=0;
22     while(!q.empty())
23     {
24         int u=q.front();
25         q.pop_front();vis[u]=0;
26         for(int v=1;v<=n;v++)
27         if(mp[u][v]!=inf&&dis[v]>dis[u]+mp[u][v])
28         {
29             dis[v]=dis[u]+mp[u][v];
30             fro[v]=u;
31             if(!vis[v])
32             {
33                 if(!q.empty()&&dis[v]<=dis[q.front()]) q.push_front(v);
34                 else q.push_back(v);
35                 vis[v]=1;
36             }
37         }
38     }
39 }
40 
41 void change(int v)
42 {
43     int u=fro[v];
44     mp[u][v]=-mp[u][v];//來時路徑取反
45     mp[v][u]=inf;//不能走了
46     if(u==1) return;//到達起點 
47     change(u); 
48 }
49 
50 int main()
51 {
52     while(scanf("%d",&n)!=EOF&&n)
53     {
54         memset(mp,inf,sizeof(mp));
55         m=rd();
56         for(int i=1;i<=m;i++)
57         {
58             int u=rd(),v=rd(),w=rd();
59             mp[u][v]=mp[v][u]=w;
60         }
61         spfa(1);int ans=dis[n];//正向跑
62         if(dis[n]==inf) {printf("Back to jail\n");continue;}
63         change(n);
64         spfa(n);//反向
65         if(dis[1]==inf) {printf("Back to jail\n");continue;}
66         else printf("%d\n",ans+dis[1]);
67     }
68     return 0;
69 }      

100昏 spfa

費用流等我徹底會了再來QAQ 

轉載于:https://www.cnblogs.com/lxyyyy/p/10392899.html