結果
問題 | No.1301 Strange Graph Shortest Path |
ユーザー | momohara |
提出日時 | 2020-11-27 22:52:13 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 210 ms / 3,000 ms |
コード長 | 4,468 bytes |
コンパイル時間 | 2,761 ms |
コンパイル使用メモリ | 214,572 KB |
実行使用メモリ | 34,916 KB |
最終ジャッジ日時 | 2023-10-09 21:44:00 |
合計ジャッジ時間 | 9,807 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,356 KB |
testcase_01 | AC | 2 ms
4,352 KB |
testcase_02 | AC | 155 ms
32,184 KB |
testcase_03 | AC | 126 ms
28,824 KB |
testcase_04 | AC | 198 ms
31,248 KB |
testcase_05 | AC | 128 ms
31,924 KB |
testcase_06 | AC | 176 ms
29,024 KB |
testcase_07 | AC | 160 ms
30,200 KB |
testcase_08 | AC | 128 ms
29,208 KB |
testcase_09 | AC | 168 ms
27,740 KB |
testcase_10 | AC | 131 ms
28,888 KB |
testcase_11 | AC | 181 ms
30,028 KB |
testcase_12 | AC | 187 ms
29,932 KB |
testcase_13 | AC | 159 ms
32,412 KB |
testcase_14 | AC | 162 ms
27,676 KB |
testcase_15 | AC | 160 ms
28,524 KB |
testcase_16 | AC | 204 ms
31,320 KB |
testcase_17 | AC | 172 ms
32,568 KB |
testcase_18 | AC | 152 ms
29,888 KB |
testcase_19 | AC | 179 ms
29,304 KB |
testcase_20 | AC | 180 ms
28,372 KB |
testcase_21 | AC | 166 ms
31,284 KB |
testcase_22 | AC | 188 ms
29,240 KB |
testcase_23 | AC | 163 ms
32,252 KB |
testcase_24 | AC | 183 ms
29,192 KB |
testcase_25 | AC | 194 ms
31,164 KB |
testcase_26 | AC | 173 ms
30,048 KB |
testcase_27 | AC | 174 ms
30,068 KB |
testcase_28 | AC | 133 ms
31,812 KB |
testcase_29 | AC | 210 ms
30,784 KB |
testcase_30 | AC | 189 ms
31,148 KB |
testcase_31 | AC | 197 ms
30,864 KB |
testcase_32 | AC | 1 ms
4,352 KB |
testcase_33 | AC | 82 ms
25,256 KB |
testcase_34 | AC | 194 ms
34,916 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; /* #include <atcoder/all> using namespace atcoder; */ #define all(hoge) (hoge).begin(), (hoge).end() #define en '\n' using ll = long long; using ull = unsigned long long; #define rep(i, m, n) for(ll i = (ll)(m); i < (ll)(n); ++i) #define rep2(i, m, n) for(ll i = (ll)(n)-1; i >= (ll)(m); --i) #define REP(i, n) rep(i, 0, n) #define REP2(i, n) rep2(i, 0, n) template <class T> using vec = vector<T>; template <class T> using vvec = vector<vec<T>>; typedef pair<ll, ll> P; using tp = tuple<ll, ll, ll>; constexpr long long INF = 1LL << 60; constexpr int INF_INT = 1 << 25; //constexpr long long MOD = (ll)1e9 + 7; constexpr long long MOD = 998244353LL; using ld = long double; static const ld pi = 3.141592653589793L; using Array = vector<ll>; using Matrix = vector<Array>; /* #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") */ template <class T> inline bool chmin(T &a, T b) { if(a > b) { a = b; return true; } return false; } template <class T> inline bool chmax(T &a, T b) { if(a < b) { a = b; return true; } return false; } template <typename flow_t, typename cost_t> struct PrimalDual { const cost_t INF; struct edge { int to; flow_t cap; cost_t cost; int rev; bool isrev; }; vector<vector<edge>> graph; vector<cost_t> potential, min_cost; vector<int> prevv, preve; PrimalDual(int V) : graph(V), INF(numeric_limits<cost_t>::max()) {} void add_edge(int from, int to, flow_t cap, cost_t cost) { graph[from].emplace_back((edge){to, cap, cost, (int)graph[to].size(), false}); graph[to].emplace_back((edge){from, 0, -cost, (int)graph[from].size() - 1, true}); } cost_t min_cost_flow(int s, int t, flow_t f) { int V = (int)graph.size(); cost_t ret = 0; using Pi = pair<cost_t, int>; priority_queue<Pi, vector<Pi>, greater<Pi>> que; potential.assign(V, 0); preve.assign(V, -1); prevv.assign(V, -1); while(f > 0) { min_cost.assign(V, INF); que.emplace(0, s); min_cost[s] = 0; while(!que.empty()) { Pi p = que.top(); que.pop(); if(min_cost[p.second] < p.first) continue; for(int i = 0; i < graph[p.second].size(); i++) { edge &e = graph[p.second][i]; cost_t nextCost = min_cost[p.second] + e.cost + potential[p.second] - potential[e.to]; if(e.cap > 0 && min_cost[e.to] > nextCost) { min_cost[e.to] = nextCost; prevv[e.to] = p.second, preve[e.to] = i; que.emplace(min_cost[e.to], e.to); } } } if(min_cost[t] == INF) return -1; for(int v = 0; v < V; v++) potential[v] += min_cost[v]; flow_t addflow = f; for(int v = t; v != s; v = prevv[v]) { addflow = min(addflow, graph[prevv[v]][preve[v]].cap); } f -= addflow; ret += addflow * potential[t]; for(int v = t; v != s; v = prevv[v]) { edge &e = graph[prevv[v]][preve[v]]; e.cap -= addflow; graph[v][e.rev].cap += addflow; } } return ret; } void output() { for(int i = 0; i < graph.size(); i++) { for(auto &e : graph[i]) { if(e.isrev) continue; auto &rev_e = graph[e.to][e.rev]; cout << i << "->" << e.to << " (flow: " << rev_e.cap << "/" << rev_e.cap + e.cap << ")" << endl; } } } }; void solve() { int n, m; cin >> n >> m; PrimalDual<int, ll> pd(n); REP(i, m) { int u, v, c, d; cin >> u >> v >> c >> d; u--; v--; pd.add_edge(u, v, 1, c); pd.add_edge(v, u, 1, c); pd.add_edge(u, v, 1, d); pd.add_edge(v, u, 1, d); } auto ans = pd.min_cost_flow(0, n - 1, 2); cout << ans << en; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); /* ll t; cin >> t; REP(i, t - 1) { solve(); }*/ solve(); return 0; }