結果
問題 | No.1301 Strange Graph Shortest Path |
ユーザー |
![]() |
提出日時 | 2020-11-28 12:40:23 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 286 ms / 3,000 ms |
コード長 | 3,699 bytes |
コンパイル時間 | 1,856 ms |
コンパイル使用メモリ | 182,088 KB |
実行使用メモリ | 34,596 KB |
最終ジャッジ日時 | 2024-09-12 22:21:52 |
合計ジャッジ時間 | 11,582 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 33 |
ソースコード
#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 cyclesint 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, false)<<endl;}