1506: Double Shortest Paths

Submit Page      Summary      Time Limit: 1 Sec       Memory Limit: 128 Mb       Submitted: 410       Solved: 134    

---

Description

Input

There will be at most 200 test cases. Each case begins with two integers n, m (1<=n<=500, 1<=m<=2000), the number of caves and passages. Each of the following m lines contains four integers u, v, di and ai (1<=u,v<=n, 1<=di<=1000, 0<=ai<=1000). Note that there can be multiple passages connecting the same pair of caves, and even passages connecting a cave and itself.

Output

For each test case, print the case number and the minimal total difficulty.

Sample Input

4 4 1 2 5 1 2 4 6 0 1 3 4 0 3 4 9 1 4 4 1 2 5 10 2 4 6 10 1 3 4 10 3 4 9 10

Sample Output

Case 1: 23 Case 2: 24

Hint

Source

湖南省第十届大学生计算机程序设计竞赛

题目大意：

给你N个点，M条有向边。现在有两个人从1走到n，问最小总路径花费。

一条边有四个元素：x，y，w，ad

表示这条边从x走到y，第一次走花费w，第二次走花费w+ad.

思路：

不能直接跑两次最短路，因为第一次跑虽然是最优的，但是第二次跑显然再跑当前最优不一定是整体最优。

所以贪心的跑两次最短路是一定不对的。

那么考虑一条边，其价值为w的，只能走一次，那么我们不妨将其看成一个网络流模型。

那么对应建边：

①从源点连入起点1，流为2，费用为0.

②从n连入汇点，流为2，费用为0.

③对于每条边拆成两条边，第一条边从x连入y，流为1，费用为w.

④对于每条边拆成两条边，第二条边从x连入y，流为1，费用为w+ad.

那么此时直接跑费用流即可。

因为题目保证了一定有解，所以我们不必担心其他。

Ac代码：

#include<stdio.h> #include<string.h> #include<queue> #include<iostream> using namespace std; struct node { int from; int to; int w; int f; int next; int num; }e[1151515]; int n,m,ss,tt,cont; int path[151515]; int pre[151515]; int head[151515]; int dis[151515]; int vis[151515]; void add(int from,int to,int w,int f) { e[cont].from=from; e[cont].to=to; e[cont].f=f; e[cont].w=w; e[cont].num=cont; e[cont].next=head[from]; head[from]=cont++; } int SPFA() { queue<int >s; s.push(ss); memset(pre,-1,sizeof(pre)); memset(path,-1,sizeof(path)); for(int i=1;i<=tt;i++)dis[i]=0x3f3f3f3f; dis[ss]=0; memset(vis,0,sizeof(vis)); vis[ss]=1; while(!s.empty()) { int u=s.front(); s.pop(); vis[u]=0; for(int i=head[u];i!=-1;i=e[i].next) { int v=e[i].to; int w=e[i].w; int f=e[i].f; if(f&&dis[v]>dis[u]+w) { dis[v]=dis[u]+w; pre[v]=u; path[v]=e[i].num; if(vis[v]==0) { s.push(v); vis[v]=1; } } } } if(dis[tt]!=0x3f3f3f3f)return 1; else return 0; } void Min_costflow() { int ans=0; int maxflow=0; while(SPFA()==1) { int minn=0x3f3f3f3f; for(int i=tt;i!=ss;i=pre[i]) { minn=min(minn,e[path[i]].f); } maxflow+=minn; ans+=dis[tt]*minn; for(int i=tt;i!=ss;i=pre[i]) { e[path[i]].f-=minn; e[path[i]^1].f+=minn; } } printf("%d\n",ans); } int main() { int kase=0; while(~scanf("%d%d",&n,&m)) { cont=0; ss=n+1; tt=ss+1; memset(head,-1,sizeof(head)); for(int i=0;i<m;i++) { int x,y,w,ad; scanf("%d%d%d%d",&x,&y,&w,&ad); add(x,y,w,1); add(y,x,-w,0); add(x,y,w+ad,1); add(y,x,-(w+ad),0); } add(ss,1,0,2);add(ss,1,0,0); add(n,tt,0,2);add(tt,n,0,0); printf("Case %d: ",++kase); Min_costflow(); } }