結果
問題 | No.1301 Strange Graph Shortest Path |
ユーザー | fura |
提出日時 | 2020-11-29 20:02:47 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 238 ms / 3,000 ms |
コード長 | 2,356 bytes |
コンパイル時間 | 2,512 ms |
コンパイル使用メモリ | 215,752 KB |
実行使用メモリ | 34,204 KB |
最終ジャッジ日時 | 2023-10-11 02:34:20 |
合計ジャッジ時間 | 11,035 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,368 KB |
testcase_01 | AC | 1 ms
4,372 KB |
testcase_02 | AC | 176 ms
32,096 KB |
testcase_03 | AC | 144 ms
29,080 KB |
testcase_04 | AC | 213 ms
30,884 KB |
testcase_05 | AC | 150 ms
31,876 KB |
testcase_06 | AC | 192 ms
28,816 KB |
testcase_07 | AC | 182 ms
30,216 KB |
testcase_08 | AC | 150 ms
29,088 KB |
testcase_09 | AC | 182 ms
27,548 KB |
testcase_10 | AC | 148 ms
28,688 KB |
testcase_11 | AC | 190 ms
29,840 KB |
testcase_12 | AC | 196 ms
29,752 KB |
testcase_13 | AC | 180 ms
32,276 KB |
testcase_14 | AC | 174 ms
27,480 KB |
testcase_15 | AC | 174 ms
28,376 KB |
testcase_16 | AC | 213 ms
30,900 KB |
testcase_17 | AC | 191 ms
32,532 KB |
testcase_18 | AC | 168 ms
29,576 KB |
testcase_19 | AC | 190 ms
29,000 KB |
testcase_20 | AC | 191 ms
28,012 KB |
testcase_21 | AC | 185 ms
31,292 KB |
testcase_22 | AC | 199 ms
28,708 KB |
testcase_23 | AC | 177 ms
32,160 KB |
testcase_24 | AC | 196 ms
28,744 KB |
testcase_25 | AC | 202 ms
31,200 KB |
testcase_26 | AC | 181 ms
29,752 KB |
testcase_27 | AC | 194 ms
29,748 KB |
testcase_28 | AC | 154 ms
31,776 KB |
testcase_29 | AC | 212 ms
30,444 KB |
testcase_30 | AC | 202 ms
30,788 KB |
testcase_31 | AC | 201 ms
30,652 KB |
testcase_32 | AC | 1 ms
4,372 KB |
testcase_33 | AC | 104 ms
25,828 KB |
testcase_34 | AC | 238 ms
34,204 KB |
ソースコード
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(n);i++) using namespace std; using lint=long long; template<class capa_t,class cost_t> class mcf_graph{ struct edge{ int to,rev; capa_t capa,flow; cost_t cost; edge(int to,int rev,const capa_t& capa,const cost_t& cost,const capa_t& flow):to(to),rev(rev),capa(capa),cost(cost),flow(flow){} }; vector<vector<edge>> G; static constexpr capa_t CAPA_INF=numeric_limits<capa_t>::max(); static constexpr cost_t COST_INF=numeric_limits<cost_t>::max(); public: mcf_graph(){} mcf_graph(int n):G(n){} void add_directed_edge(int u,int v,const capa_t& capa,const cost_t& cost){ G[u].emplace_back(v,G[v].size() ,capa, cost,0); G[v].emplace_back(u,G[u].size()-1, 0,-cost,0); } pair<capa_t,cost_t> minimum_cost_flow(int s,int t,capa_t limit=CAPA_INF){ int n=G.size(); vector<int> pre(n); vector<cost_t> d(n),pot(n); priority_queue<pair<cost_t,int>> Q; auto augment=[&]()->pair<capa_t,cost_t>{ rep(u,n) d[u]=(u==s?0:COST_INF); // Dijkstra bool ok=false; Q.emplace(0,s); while(!Q.empty()){ int u; cost_t tmp; tie(tmp,u)=Q.top(); Q.pop(); if(-tmp<d[u]) continue; if(u==t) ok=true; for(const edge& e:G[u]) if(e.capa-e.flow>0) { cost_t cost2=d[u]+e.cost+pot[u]-pot[e.to]; if(d[e.to]>cost2){ d[e.to]=cost2; pre[e.to]=e.rev; Q.emplace(-cost2,e.to); } } } if(!ok) return {0,0}; capa_t water=limit; for(int u=t;u!=s;){ edge& e1=G[u][pre[u]]; edge& e2=G[e1.to][e1.rev]; water=min(water,e2.capa-e2.flow); u=e1.to; } limit-=water; for(int u=t;u!=s;){ edge& e1=G[u][pre[u]]; edge& e2=G[e1.to][e1.rev]; e1.flow-=water; e2.flow+=water; u=e1.to; } rep(u,n) pot[u]+=d[u]; return {water,water*pot[t]}; }; capa_t res1=0; cost_t res2=0; while(limit>0){ auto tmp=augment(); if(tmp.first==0) break; res1+=tmp.first; res2+=tmp.second; } return {res1,res2}; } }; int main(){ int n,m; scanf("%d%d",&n,&m); mcf_graph<int,lint> G(n); rep(i,m){ int u,v; lint c1,c2; scanf("%d%d%lld%lld",&u,&v,&c1,&c2); u--; v--; G.add_directed_edge(u,v,1,c1); G.add_directed_edge(u,v,1,c2); G.add_directed_edge(v,u,1,c1); G.add_directed_edge(v,u,1,c2); } printf("%lld\n",G.minimum_cost_flow(0,n-1,2).second); return 0; }