1 #include <cstdio>   2 #include <cstring>   3 #include <iostream>   4 #include <algorithm>   5 #define M 510   6 #define S 1   7 #define T n   8 #define INF 1000000000  9 using namespace std;  10 struct edge{  11     int x,y,f,c;  12 }e[124800];  13 int n,m,ans,i,j,k,x,y,z;  14 int map[M][M];15 int head[M],tot=1;16 int dpt[M]; 17 struct abcd{  18     int to,next,f;  19 }table[124800<<2];20 void add(int x,int y,int z)  21 {  22     table[++tot].to=y;  23     table[tot].f=z;  24     table[tot].next=head[x];  25     head[x]=tot;  26     table[++tot].to=x;  27     table[tot].f=0;  28     table[tot].next=head[y];  29     head[y]=tot; 30 }  31     bool bfs()  32     {  33         static int q[M];  34         int i,r=0,h=0;  35         memset(dpt,-1,sizeof dpt);  36         dpt[S]=1;q[++r]=S;  37         while(r!=h)  38         {  39             int x=q[++h];  40             for(i=head[x];i;i=table[i].next)  41                 if(table[i].f&&!~dpt[table[i].to])  42                 {  43                     dpt[table[i].to]=dpt[x]+1;  44                     q[++r]=table[i].to;  45                     if(table[i].to==T)  46                         return true;  47                 }  48         }  49         return false;  50     }  51     int dfs(int x,int flow)  52     {  53         int i,left=flow;  54         if(x==T) return flow;  55         for(i=head[x];i&&left;i=table[i].next)  56             if(table[i].f&&dpt[table[i].to]==dpt[x]+1)  57             {  58                 int temp=dfs(table[i].to,min(left,table[i].f) );  59                 left-=temp;  60                 table[i].f-=temp;  61                 table[i^1].f+=temp;  62             }  63         if(left) dpt[x]=-1;  64      return flow-left;  65     }  66 int main()  67 {  68     scanf("%d%d",&n,&m);69     for(int i=1;i<=n;i++)70         for(int j=1;j<=n;j++)71             map[i][j]=INF;72     for(i=1;i<=n;i++)  73         map[i][i]=0;  74     for(i=1;i<=m;i++)  75     {  76         scanf("%d%d%d%d",&x,&y,&z,&e[i].c);  77         e[i].x=x;e[i].y=y;e[i].f=z;  78         map[x][y]=map[y][x]=z;  79     }  80     for(k=1;k<=n;k++)  81         for(i=1;i<=n;i++)  82             for(j=1;j<=n;j++)  83                 map[i][j]=min(map[i][j],map[i][k]+map[k][j]);  84     printf("%d\n",map[1][n]);85     for(i=1;i<=m;i++)  86     {  87         x=e[i].x;y=e[i].y;z=e[i].f;  88         if( map[1][x]+map[y][n]+z==map[1][n] )  89             add(x,y,e[i].c);  90         if( map[1][y]+map[x][n]+z==map[1][n] )  91             add(y,x,e[i].c);  92     }  93     while( bfs() )  94         ans+=dfs(1,INF);  95     printf("%d",ans);96     return 0;  97 }