【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