結果
問題 | No.1301 Strange Graph Shortest Path |
ユーザー | kotatsugame |
提出日時 | 2020-11-28 03:52:45 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 307 ms / 3,000 ms |
コード長 | 1,803 bytes |
コンパイル時間 | 1,067 ms |
コンパイル使用メモリ | 88,620 KB |
実行使用メモリ | 34,708 KB |
最終ジャッジ日時 | 2023-10-09 23:26:44 |
合計ジャッジ時間 | 11,588 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,348 KB |
testcase_01 | AC | 2 ms
4,372 KB |
testcase_02 | AC | 247 ms
32,700 KB |
testcase_03 | AC | 206 ms
29,240 KB |
testcase_04 | AC | 307 ms
31,408 KB |
testcase_05 | AC | 224 ms
32,364 KB |
testcase_06 | AC | 281 ms
29,232 KB |
testcase_07 | AC | 253 ms
30,788 KB |
testcase_08 | AC | 210 ms
29,520 KB |
testcase_09 | AC | 263 ms
27,664 KB |
testcase_10 | AC | 216 ms
29,336 KB |
testcase_11 | AC | 283 ms
30,084 KB |
testcase_12 | AC | 279 ms
30,244 KB |
testcase_13 | AC | 248 ms
33,012 KB |
testcase_14 | AC | 246 ms
27,840 KB |
testcase_15 | AC | 245 ms
28,976 KB |
testcase_16 | AC | 307 ms
31,376 KB |
testcase_17 | AC | 267 ms
33,304 KB |
testcase_18 | AC | 237 ms
30,240 KB |
testcase_19 | AC | 273 ms
29,300 KB |
testcase_20 | AC | 271 ms
28,412 KB |
testcase_21 | AC | 256 ms
31,856 KB |
testcase_22 | AC | 282 ms
29,408 KB |
testcase_23 | AC | 253 ms
32,984 KB |
testcase_24 | AC | 278 ms
29,068 KB |
testcase_25 | AC | 294 ms
31,304 KB |
testcase_26 | AC | 260 ms
30,168 KB |
testcase_27 | AC | 273 ms
30,260 KB |
testcase_28 | AC | 225 ms
32,248 KB |
testcase_29 | AC | 299 ms
30,704 KB |
testcase_30 | AC | 288 ms
31,308 KB |
testcase_31 | AC | 298 ms
30,760 KB |
testcase_32 | AC | 2 ms
4,348 KB |
testcase_33 | AC | 154 ms
25,360 KB |
testcase_34 | AC | 276 ms
34,708 KB |
コンパイルメッセージ
a.cpp:5:1: 警告: ISO C++ では型の無い ‘main’ の宣言を禁止しています [-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; }