結果
問題 | No.1301 Strange Graph Shortest Path |
ユーザー | carrot46 |
提出日時 | 2020-11-28 12:26:16 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,692 bytes |
コンパイル時間 | 2,030 ms |
コンパイル使用メモリ | 180,288 KB |
実行使用メモリ | 35,376 KB |
最終ジャッジ日時 | 2023-10-09 23:52:23 |
合計ジャッジ時間 | 18,234 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
35,376 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 311 ms
32,764 KB |
testcase_03 | AC | 260 ms
29,016 KB |
testcase_04 | AC | 358 ms
31,172 KB |
testcase_05 | AC | 262 ms
32,224 KB |
testcase_06 | AC | 314 ms
29,112 KB |
testcase_07 | AC | 309 ms
31,192 KB |
testcase_08 | AC | 250 ms
29,724 KB |
testcase_09 | AC | 310 ms
27,692 KB |
testcase_10 | AC | 262 ms
29,280 KB |
testcase_11 | AC | 327 ms
30,108 KB |
testcase_12 | AC | 328 ms
30,008 KB |
testcase_13 | AC | 301 ms
33,036 KB |
testcase_14 | AC | 290 ms
27,828 KB |
testcase_15 | AC | 302 ms
28,816 KB |
testcase_16 | AC | 355 ms
30,936 KB |
testcase_17 | AC | 325 ms
33,044 KB |
testcase_18 | AC | 289 ms
30,132 KB |
testcase_19 | AC | 336 ms
29,212 KB |
testcase_20 | AC | 314 ms
28,248 KB |
testcase_21 | AC | 322 ms
31,748 KB |
testcase_22 | AC | 336 ms
28,884 KB |
testcase_23 | AC | 324 ms
32,736 KB |
testcase_24 | AC | 324 ms
28,824 KB |
testcase_25 | AC | 351 ms
31,244 KB |
testcase_26 | AC | 313 ms
30,176 KB |
testcase_27 | AC | 327 ms
30,260 KB |
testcase_28 | AC | 283 ms
32,160 KB |
testcase_29 | AC | 385 ms
30,256 KB |
testcase_30 | AC | 354 ms
31,120 KB |
testcase_31 | AC | 375 ms
30,812 KB |
testcase_32 | AC | 1 ms
4,372 KB |
testcase_33 | AC | 167 ms
26,268 KB |
testcase_34 | TLE | - |
ソースコード
#include <bits/stdc++.h> //#include <chrono> //#pragma GCC optimize("O3") using namespace std; #define reps(i,s,n) for(int i = s; i < n; i++) #define rep(i,n) reps(i,0,n) #define Rreps(i,n,e) for(int i = n - 1; i >= e; --i) #define Rrep(i,n) Rreps(i,n,0) #define ALL(a) a.begin(), a.end() using ll = long long; using vec = vector<ll>; using mat = vector<vec>; ll N,M,H,W,Q,K,A,B; string S; using P = pair<ll, ll>; const ll INF = (1LL<<60); template<class T> bool chmin(T &a, const T &b){ if(a > b) {a = b; return true;} else return false; } template<class T> bool chmax(T &a, const T &b){ if(a < b) {a = b; return true;} else return false; } struct edge{ int to, cap, rev; ll cost; edge(){} edge(int a, int b, ll c, int d){ to = a; cap = b; cost = c; rev = d; } }; using ve = vector<edge>; void add_edge(int from, int to, int cap, ll cost, vector<ve> &G, bool directed = true){ rep(_, (directed ? 1 : 2)) { G[from].emplace_back(to, cap, cost, (int) G[to].size()); G[to].emplace_back(from, 0, -cost, (int) G[from].size() - 1); swap(to, from); } } bool bellman_ford_for_flow(int s, vector<ve> &G, vec &dist){ //O(|V|^2 + |V||E|) dist[s] = 0; int num(0), sz = G.size(); while(num++ < sz){ bool update = false; rep(v, sz){ if(dist[v] != INF) { for (edge &e : G[v]) { if (e.cap > 0 && chmin(dist[e.to], dist[v] + e.cost)) update = true; } } } if(!update) return true; } return false; //failed } void dijkstra_for_flow(int s, vector<ve> &G, vec &h, vec &dist, vector<int> &prev_v, vector<int> &prev_e){ typedef struct _comp{ ll cost; int v; _comp(){} _comp(ll a, int b){ cost = a; v = b; } bool operator > (const _comp a){ return cost > a.cost; } } mp; priority_queue<mp, vector<mp>, greater<> > pque; dist[s] = 0; pque.emplace(0, s); while(!pque.empty()){ mp p = pque.top(); pque.pop(); if(dist[p.v] < p.cost) continue; rep(i, (int)G[p.v].size()){ edge &e = G[p.v][i]; if(e.cap > 0 && chmin(dist[e.to], p.cost + e.cost + h[p.v] - h[e.to])){ prev_v[e.to] = p.v; prev_e[e.to] = i; pque.emplace(dist[e.to], e.to); } } } } //全然Validateできていないので注意 ll min_cost_flow(int s, int t, int f, vector<ve> &G, bool minus_exist = true){ //minus_exist : if (edge.cost < 0) //for graph without negative cycles int sz = G.size(); ll res(0); vector<int> prev_v(sz), prev_e(sz); vec h(sz, minus_exist ? INF : 0); if(minus_exist && (!bellman_ford_for_flow(s, G, h) || h[t] == INF)) return -1; while(f > 0){ vec dist(sz, INF); dijkstra_for_flow(s, G, h, dist, prev_v, prev_e); if(dist[t] == INF) return -1; rep(v, sz) h[v] += dist[v]; int d = f; for(int v = t; v != s; v = prev_v[v]){ chmin(d, G[prev_v[v]][prev_e[v]].cap); } f -= d; res += h[t] * d; for(int v = t; v != s; v = prev_v[v]){ edge &e = G[prev_v[v]][prev_e[v]]; e.cap -= d; G[v][e.rev].cap += d; } } return res; } int main(){ cin>>N>>M; vector<ve> G(N); rep(i, M){ int u, v, c, d; cin>>u>>v>>c>>d; --u; --v; add_edge(u, v, 1, c, G, false); add_edge(u, v, 1, d, G, false); } cout<<min_cost_flow(0, N - 1, 2, G)<<endl; }