Problem: Examples

Input

4 5 2
0 1 2 1
0 2 1 2
1 2 1 1
1 3 1 3
2 3 2 1


Output

6


Input




Output

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
using UL=unsigned int;
using LL=long long;
using ULL=unsigned long long;
#define rep(i,n) for(UL i=0; i<(n); i++)

template<class T>
using nega_queue = priority_queue<T,vector<T>,greater<T>>;

struct Edge{ UL u,v; UL c; int d; UL r; };

UL N,M;
Edge J[2000];
vector<UL> E[100];

UL F;
int fAns = 0;
UL fD[100];
UL fPE[100];
UL fP[100]={};

void fDijkstra(){
 rep(i,N) fD[i]=fPE[i]=~0u;
 nega_queue<pair<UL,pair<UL,UL>>> Q; Q.push({0,{0,~0u}});
 while(Q.size()){
  UL d=Q.top().first;
  UL p=Q.top().second.first;
  UL pre=Q.top().second.second;
  Q.pop();
  if(fD[p]!=~0u) continue;
  fD[p]=d;
  fPE[p]=pre;
  for(UL j:E[p]){
   if(J[j].c==0)continue;
   Q.push({d+J[j].d+fP[p]-fP[J[j].v],{J[j].v,j}});
  }
 }
 rep(i,N) fP[i]+=fD[i];
}

void flow(){
 fDijkstra();
 if(fD[N-1]==~0u){ F=0; fAns=-1; return; }
 UL p=N-1;
 UL c=F;
 while(p!=0){
  c=min(c,J[fPE[p]].c);
  p=J[fPE[p]].u;
 }
 p=N-1;
 while(p!=0){
  J[fPE[p]].c-=c;
  J[J[fPE[p]].r].c+=c;
  fAns += (int)c * J[fPE[p]].d;
  p=J[fPE[p]].u;
 }
 F-=c;
}

int main(){
 scanf("%u%u%u",&N,&M,&F);
 rep(i,M){
  UL u,v,c; int d; scanf("%u%u%u%d",&u,&v,&c,&d);
  E[u].push_back(i);
  E[v].push_back(M+i);
  J[i]=Edge{u,v,c,d,M+i};
  J[M+i]=Edge{v,u,0,-d,i};
 }

 while(F) flow();

 printf("%d\n",fAns);

 return 0;
}