結果
問題 | No.1301 Strange Graph Shortest Path |
ユーザー | firiexp |
提出日時 | 2020-11-27 23:46:45 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 201 ms / 3,000 ms |
コード長 | 3,135 bytes |
コンパイル時間 | 1,178 ms |
コンパイル使用メモリ | 113,168 KB |
実行使用メモリ | 34,808 KB |
最終ジャッジ日時 | 2023-10-09 21:34:04 |
合計ジャッジ時間 | 8,839 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,372 KB |
testcase_01 | AC | 2 ms
4,352 KB |
testcase_02 | AC | 153 ms
32,856 KB |
testcase_03 | AC | 124 ms
29,384 KB |
testcase_04 | AC | 198 ms
31,364 KB |
testcase_05 | AC | 126 ms
32,432 KB |
testcase_06 | AC | 169 ms
29,540 KB |
testcase_07 | AC | 160 ms
31,256 KB |
testcase_08 | AC | 127 ms
29,656 KB |
testcase_09 | AC | 169 ms
27,888 KB |
testcase_10 | AC | 129 ms
29,412 KB |
testcase_11 | AC | 174 ms
30,080 KB |
testcase_12 | AC | 182 ms
30,200 KB |
testcase_13 | AC | 156 ms
33,068 KB |
testcase_14 | AC | 162 ms
28,180 KB |
testcase_15 | AC | 157 ms
29,024 KB |
testcase_16 | AC | 198 ms
31,384 KB |
testcase_17 | AC | 166 ms
33,272 KB |
testcase_18 | AC | 148 ms
29,932 KB |
testcase_19 | AC | 179 ms
29,480 KB |
testcase_20 | AC | 179 ms
28,404 KB |
testcase_21 | AC | 166 ms
31,924 KB |
testcase_22 | AC | 187 ms
29,116 KB |
testcase_23 | AC | 159 ms
32,784 KB |
testcase_24 | AC | 182 ms
29,132 KB |
testcase_25 | AC | 188 ms
31,316 KB |
testcase_26 | AC | 168 ms
30,068 KB |
testcase_27 | AC | 166 ms
30,164 KB |
testcase_28 | AC | 131 ms
32,284 KB |
testcase_29 | AC | 201 ms
30,752 KB |
testcase_30 | AC | 183 ms
31,380 KB |
testcase_31 | AC | 185 ms
31,004 KB |
testcase_32 | AC | 2 ms
4,352 KB |
testcase_33 | AC | 87 ms
26,008 KB |
testcase_34 | AC | 184 ms
34,808 KB |
ソースコード
#include <iostream> #include <algorithm> #include <map> #include <set> #include <queue> #include <stack> #include <numeric> #include <bitset> #include <cmath> static const int MOD = 1000000007; using ll = long long; using u32 = unsigned; using u64 = unsigned long long; using namespace std; template<class T> constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208; template<typename F, typename C> struct PrimalDual { struct edge { int to; F cap; C cost; int rev; edge() = default; edge(int to, F cap, C cost, int rev):to(to), cap(cap), cost(cost), rev(rev) {}; }; vector<vector<edge>> G; vector<C> potential, min_cost; vector<int> prevv, preve; explicit PrimalDual(int n) : G(n), potential(n), min_cost(n), prevv(n), preve(n) {} void add_edge(int u, int v, F cap, C cost){ G[u].emplace_back(v, cap, cost, G[v].size()); G[v].emplace_back(u, 0, -cost, G[u].size()-1); } struct P{ C first; int second; P(C first,int second):first(first),second(second){} bool operator<(const P&a) const{return a.first<first;} }; void dijkstra(int s){ priority_queue<P> Q; fill(min_cost.begin(),min_cost.end(), INF<C>); min_cost[s] = 0; Q.emplace(0, s); while(!Q.empty()){ P p = Q.top(); Q.pop(); int v = p.second; if(min_cost[v] < p.first) continue; for(int i = 0; i < G[v].size(); ++i){ edge &e=G[v][i]; if(e.cap==0) continue; if(min_cost[v]+e.cost+potential[v]-potential[e.to] < min_cost[e.to]){ min_cost[e.to] = min_cost[v]+e.cost+potential[v]-potential[e.to]; prevv[e.to] = v; preve[e.to] = i; Q.emplace(min_cost[e.to], e.to); } } } } C flow(int s, int t, F fl, int &ok){ C res = 0; fill(potential.begin(),potential.end(), 0); while(fl > 0){ dijkstra(s); if(min_cost[t] == INF<C>){ ok = 0; return res; } for (int i = 0; i < potential.size(); ++i) { if(min_cost[i] < INF<C>) potential[i] += min_cost[i]; } F d = fl; for(int v = t; v != s; v = prevv[v]){ d = min(d, G[prevv[v]][preve[v]].cap); } fl -= d; res += potential[t]*d; for(int v = t; v != s; v = prevv[v]){ G[prevv[v]][preve[v]].cap -= d; G[v][G[prevv[v]][preve[v]].rev].cap += d; } } ok = 1; return res; } }; int main() { int n, m; cin >> n >> m; PrimalDual<int, ll> G(n); for (int i = 0; i < m; ++i) { int u, v, c, d; scanf("%d %d %d %d", &u, &v, &c, &d); u--; v--; G.add_edge(u, v, 1, c); G.add_edge(v, u, 1, c); G.add_edge(u, v, 1, d); G.add_edge(v, u, 1, d); } int ret = 0; cout << G.flow(0, n-1, 2, ret) << "\n"; return 0; }