結果
問題 | No.1301 Strange Graph Shortest Path |
ユーザー |
|
提出日時 | 2020-11-27 23:46:45 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 285 ms / 3,000 ms |
コード長 | 3,135 bytes |
コンパイル時間 | 1,354 ms |
コンパイル使用メモリ | 111,448 KB |
最終ジャッジ日時 | 2025-01-16 08:42:24 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 33 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:99:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 99 | scanf("%d %d %d %d", &u, &v, &c, &d); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#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;}