CSU 1506 Double Shortest Paths

1506: Double Shortest Paths

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 49 Solved: 5

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

Sample Output

Case 1: 23

Case 2: 24

HINT

Source

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

解题：费用流

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <climits>

 #include <vector>

 #include <queue>

 #include <cstdlib>

 #include <string>

 #include <set>

 #include <stack>

 #define LL long long

 #define pii pair<int,int>

 #define INF 0x3f3f3f3f

 using namespace std;

 const int maxn = ;

 struct arc{

     int to,flow,cost,next;

     arc(int x = ,int y = ,int z = ,int nxt = -){

         to = x;

         flow = y;

         cost = z;

         next = nxt;

     }

 };

 arc e[maxn*maxn];

 int head[maxn],d[maxn],p[maxn];

 int tot,S,T;

 void add(int u,int v,int flow,int cost){

     e[tot] = arc(v,flow,cost,head[u]);

     head[u] = tot++;

     e[tot] = arc(u,,-cost,head[v]);

     head[v] = tot++;

 }

 bool in[maxn];

 bool spfa(){

     queue<int>q;

     for(int i = S; i <= T; ++i){

         p[i] = -;

         in[i] = false;

         d[i] = INF;

     }

     d[S] = ;

     q.push(S);

     while(!q.empty()){

         int u = q.front();

         q.pop();

         in[u] = false;

         for(int i = head[u]; ~i; i = e[i].next){

             if(e[i].flow && d[e[i].to] > d[u] + e[i].cost){

                 d[e[i].to] = d[u] + e[i].cost;

                 p[e[i].to] = i;

                 if(!in[e[i].to]){

                     in[e[i].to] = true;

                     q.push(e[i].to);

                 }

             }

         }

     }

     return p[T] > -;

 }

 int solve(){

     int ans = ;

     while(spfa()){

         int minF = INF;

         for(int i = p[T]; ~i; i = p[e[i^].to])

             minF = min(minF,e[i].flow);

         for(int i = p[T]; ~i; i = p[e[i^].to]){

             e[i].flow -= minF;

             e[i^].flow += minF;

         }

         ans += d[T]*minF;

     }

     return ans;

 }

 int main(){

     int n,m,u,v,ai,di,cs = ;

     while(~scanf("%d %d",&n,&m)){

         memset(head,-,sizeof(head));

         S = tot = ;

         T = n + ;

         for(int i = ; i < m; ++i){

             scanf("%d %d %d %d",&u,&v,&ai,&di);

             add(u,v,,ai);

             add(u,v,,ai+di);

         }

         add(S,,,);

         add(n,T,,);

         printf("Case %d: %d\n",cs++,solve());

     }

     return ;

 }

巴特西