結果
問題 | No.1301 Strange Graph Shortest Path |
ユーザー |
|
提出日時 | 2020-11-28 03:52:45 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 291 ms / 3,000 ms |
コード長 | 1,803 bytes |
コンパイル時間 | 1,317 ms |
コンパイル使用メモリ | 88,988 KB |
実行使用メモリ | 35,324 KB |
最終ジャッジ日時 | 2024-09-12 21:56:33 |
合計ジャッジ時間 | 10,908 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 33 |
コンパイルメッセージ
a.cpp:5:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
ソースコード
#line 1 "a.cpp"#include<iostream>using namespace std;#line 1 "/home/kotatsugame/library/graph/MCF.cpp"//Minimum Cost Flow O(FE log V)#include<algorithm>#include<utility>#include<vector>#include<queue>#include<limits>template<typename T>struct MCF{struct edge{int to,rev,cap;T cost;};vector<vector<edge> >G;vector<T>h,d;vector<int>pv,pe;MCF(int n_=0):G(n_),h(n_,0),d(n_),pv(n_),pe(n_){}void add_edge(int from,int to,int cap,T cost){G[from].push_back({to,(int)G[to].size(),cap,cost});G[to].push_back({from,(int)G[from].size()-1,0,-cost});}T min_cost_flow(int s,int t,int f)//ans or -1{T ret=0;while(f>0){priority_queue<pair<T,int>,vector<pair<T,int> >,greater<pair<T,int> > >P;fill(d.begin(),d.end(),numeric_limits<T>::max());d[s]=0;P.push(make_pair(0,s));while(!P.empty()){pair<T,int>p=P.top();P.pop();if(d[p.second]<p.first)continue;for(int i=0;i<G[p.second].size();i++){edge&e=G[p.second][i];if(e.cap>0&&d[e.to]>d[p.second]+e.cost+h[p.second]-h[e.to]){d[e.to]=d[p.second]+e.cost+h[p.second]-h[e.to];pv[e.to]=p.second;pe[e.to]=i;P.push(make_pair(d[e.to],e.to));}}}if(d[t]==numeric_limits<T>::max())return -1;for(int u=0;u<G.size();u++)h[u]+=d[u];int d=f;for(int u=t;u!=s;u=pv[u])d=min(d,G[pv[u]][pe[u]].cap);f-=d;ret+=d*h[t];for(int u=t;u!=s;u=pv[u]){G[pv[u]][pe[u]].cap-=d;G[u][G[pv[u]][pe[u]].rev].cap+=d;}}return ret;}};#line 4 "a.cpp"int N,M;main(){cin>>N>>M;MCF<long>P(N);for(int i=0;i<M;i++){int u,v,c,d;cin>>u>>v>>c>>d;u--,v--;P.add_edge(u,v,1,c);P.add_edge(u,v,1,d);P.add_edge(v,u,1,c);P.add_edge(v,u,1,d);}cout<<P.min_cost_flow(0,N-1,2)<<endl;}