#include <cstdio> #include <queue> #include <cstring> using namespace std; //---------------------以下为SSSP----------------------- const int maxn=1000010; const int inf=0x3f3f3f3f; int to[maxn],nxt[maxn],f[maxn],t[maxn],c[maxn]; int n,m,tot=1,edge[maxn],d[maxn]; inline void add(int u,int v,int ti,int co) { to[tot]=v; nxt[tot]=f[u]; t[tot]=ti; c[tot]=co; f[u]=tot++; } void spfa() { queue<int>q; memset(d,0x3f,sizeof(d)); memset(edge,0,sizeof(edge)); q.push(1); d[1]=0; while(!q.empty()) { int now=q.front(); q.pop(); edge[now]=0; for (int i=f[now];i;i=nxt[i]) { if (d[to[i]]>d[now]+t[i]) { d[to[i]]=d[now]+t[i]; if (edge[to[i]]==0) { q.push(to[i]); edge[to[i]]=1; } } } } } //-------------------以上为SSSP------------------------ //-------------------以下为dinic----------------------- int head_dinic[maxn],edge_dinic[maxn],ver_dinic[maxn],d_dinic[maxn],nxt_dinic[maxn]; int tot_dinic,n_dinic,m_dinic,s_dinic,t_dinic,maxflow; queue<int> q_dinic; void add_dinic(int x,int y,int z) { ver_dinic[++tot_dinic]=y,edge_dinic[tot_dinic]=z;nxt_dinic[tot_dinic]=head_dinic[x],head_dinic[x]=tot_dinic; ver_dinic[++tot_dinic]=x,edge_dinic[tot_dinic]=0;nxt_dinic[tot_dinic]=head_dinic[y],head_dinic[y]=tot_dinic; } bool bfs() { memset(d_dinic,0,sizeof(d_dinic)); while (q_dinic.size()) q_dinic.pop(); q_dinic.push(s_dinic);d_dinic[s_dinic]=1; while (q_dinic.size()) { int x=q_dinic.front();q_dinic.pop(); for (int i=head_dinic[x];i;i=nxt_dinic[i]) { if (edge_dinic[i]&&!d_dinic[ver_dinic[i]]) { q_dinic.push(ver_dinic[i]); d_dinic[ver_dinic[i]]=d_dinic[x]+1; if (ver_dinic[i]==t_dinic) return 1; } } } return 0; } int dinic(int x,int flow) { if (x==t_dinic) return flow; int rest=flow,k; for (int i=head_dinic[x];i&&rest;i=nxt_dinic[i]) { if (edge_dinic[i]&&d_dinic[ver_dinic[i]]==d_dinic[x]+1) { k=dinic(ver_dinic[i],min(rest,edge_dinic[i])); if (!k) d_dinic[ver_dinic[i]]=0; edge_dinic[i]-=k; edge_dinic[i^1]+=k; rest-=k; } } return flow-rest; } //------------------以上为dinic------------------------ int main() { scanf("%d %d",&n,&m); s_dinic=1; t_dinic=n; for (int i=1;i<=m;i++) { int x,y,z,c; scanf("%d %d %d %d",&x,&y,&z,&c); add(x,y,z,c); add(y,x,z,c); } spfa(); tot_dinic=1; printf("%d\n",d[n]); for (int i=1;i<=n;i++) for (int j=f[i];j;j=nxt[j]) if(d[to[j]]==d[i]+t[j]) //printf("%d %d %d\n",i,ver[j],ca[j]), add_dinic(i,to[j],c[j]); int flow=0; while (bfs()) while (flow=dinic(s_dinic,inf)) maxflow+=flow; printf("%d\n",maxflow); return 0; }