結果
問題 | No.1301 Strange Graph Shortest Path |
ユーザー |
![]() |
提出日時 | 2020-11-27 22:59:15 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 225 ms / 3,000 ms |
コード長 | 9,756 bytes |
コンパイル時間 | 2,704 ms |
コンパイル使用メモリ | 215,388 KB |
最終ジャッジ日時 | 2025-01-16 08:18:42 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 33 |
ソースコード
// >>> TEMPLATES#include <bits/stdc++.h>using namespace std;using ll = long long;using ld = long double;using i32 = int32_t;using i64 = int64_t;using u32 = uint32_t;using u64 = uint64_t;#define int ll#define double ld#define rep(i,n) for (int i = 0; i < (int)(n); i++)#define rep1(i,n) for (int i = 1; i <= (int)(n); i++)#define repR(i,n) for (int i = (int)(n)-1; i >= 0; i--)#define rep1R(i,n) for (int i = (int)(n); i >= 1; i--)#define loop(i,a,B) for (int i = a; i B; i++)#define loopR(i,a,B) for (int i = a; i B; i--)#define all(x) begin(x), end(x)#define allR(x) rbegin(x), rend(x)#define rng(x,l,r) begin(x) + (l), begin(x) + (r)#define pb push_back#define eb emplace_back#define mp make_pair#define fst first#define snd secondtemplate <class Int> auto constexpr inf = numeric_limits<Int>::max()/2-1;auto constexpr INF32 = inf<int32_t>;auto constexpr INF64 = inf<int64_t>;auto constexpr INF = inf<int>;#ifdef LOCAL#include "debug.hpp"#else#define dump(...) (void)(0)#define say(x) (void)(0)#define debug if (0)#endiftemplate <class T, class Comp> struct pque : priority_queue<T, vector<T>, Comp> {vector<T> &data() { return this->c; }void clear() { this->c.clear(); }};template <class T> using pque_max = pque<T, less<T>>;template <class T> using pque_min = pque<T, greater<T>>;template <class T, class = typename T::iterator, enable_if_t<!is_same<T, string>::value, int> = 0>ostream& operator<<(ostream& os, T const& a) { bool f = true; for (auto const& x : a) os << (f ? "" : " ") << x, f = false; return os; }template <class T, size_t N, enable_if_t<!is_same<T, char>::value, int> = 0>ostream& operator<<(ostream& os, const T (&a)[N]) { bool f = true; for (auto const& x : a) os << (f ? "" : " ") << x, f = false; return os; }template <class T, class = decltype(begin(declval<T&>())), class = typename enable_if<!is_same<T, string>::value>::type>istream& operator>>(istream& is, T &a) { for (auto& x : a) is >> x; return is; }template <class T, class S> ostream& operator<<(ostream& os, pair<T,S> const& p) { return os << p.first << " " << p.second; }template <class T, class S> istream& operator>>(istream& is, pair<T,S>& p) { return is >> p.first >> p.second; }struct IOSetup { IOSetup() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } iosetup;template <class F> struct FixPoint : private F {constexpr FixPoint(F&& f) : F(forward<F>(f)) {}template <class... T> constexpr auto operator()(T&&... x) const { return F::operator()(*this, forward<T>(x)...); }};struct MakeFixPoint { template <class F> constexpr auto operator|(F&& f) const { return FixPoint<F>(forward<F>(f)); } };#define MFP MakeFixPoint()|#define def(name, ...) auto name = MFP [&](auto &&name, __VA_ARGS__)template <class T, size_t d> struct vec_impl {using type = vector<typename vec_impl<T,d-1>::type>;template <class... U> static type make_v(size_t n, U&&... x) { return type(n, vec_impl<T,d-1>::make_v(forward<U>(x)...)); }};template <class T> struct vec_impl<T,0> { using type = T; static type make_v(T const& x = {}) { return x; } };template <class T, size_t d = 1> using vec = typename vec_impl<T,d>::type;template <class T, size_t d = 1, class... Args> auto make_v(Args&&... args) { return vec_impl<T,d>::make_v(forward<Args>(args)...); }template <class T> void quit(T const& x) { cout << x << endl; exit(0); }template <class T, class U> constexpr bool chmin(T& x, U const& y) { if (x > y) { x = y; return true; } return false; }template <class T, class U> constexpr bool chmax(T& x, U const& y) { if (x < y) { x = y; return true; } return false; }template <class It> constexpr auto sumof(It b, It e) { return accumulate(b, e, typename iterator_traits<It>::value_type{}); }template <class T> int sz(T const& x) { return x.size(); }template <class C, class T> int lbd(C const& v, T const& x) { return lower_bound(begin(v), end(v), x)-begin(v); }template <class C, class T> int ubd(C const& v, T const& x) { return upper_bound(begin(v), end(v), x)-begin(v); }const int dx[] = { 1,0,-1,0,1,-1,-1,1 };const int dy[] = { 0,1,0,-1,1,1,-1,-1 };constexpr int popcnt(ll x) { return __builtin_popcountll(x); }// [a,b]template <class Int> Int rand(Int a, Int b) { static mt19937_64 mt{random_device{}()}; return uniform_int_distribution<Int>(a,b)(mt); }i64 irand(i64 a, i64 b) { return rand<i64>(a,b); }u64 urand(u64 a, u64 b) { return rand<u64>(a,b); }// <<<// >>> min cost flowtemplate <class Flow, class Cost>struct MinCostFlow { // Primal-Dualstatic constexpr Cost inf = numeric_limits<Cost>::max();static constexpr Flow EPS = 1e-10; //struct Edge {int32_t to, rev, id;Flow cap;Cost cost;Edge(int to, int rev, int id, Flow cap, Cost cost): to(to), rev(rev), id(id), cap(cap), cost(cost) {}};vector<vector<Edge>> g;vector<pair<int32_t,int32_t>> es;vector<Cost> h; // potentialvector<int32_t> pv, pe; // previous vertex/edge indexint V, E = 0, s = -1, t = -1;Flow next_cap = 0;Cost next_cost = 0;bool neg_edge = false;MinCostFlow(int V = 0) : g(V), h(V), pv(V, -1), pe(V, -1), V(V) {}void add_edge(int from, int to, Flow cap, Cost cost) {assert(from != to);es.emplace_back(from, g[from].size());g[from].emplace_back(to, g[to].size(), E, cap, cost);g[to].emplace_back(from, g[from].size()-1, E, 0, -cost);E++;if (cost < -EPS) neg_edge = true;}struct edge_t {int32_t from, to;Flow flow, cap;Cost cost;};Edge& internal_edge(int id) {assert(0 <= id); assert(id < (int)es.size());int from, idx; tie(from, idx) = es[id];return g[from][idx];}edge_t edge(int id) const {assert(0 <= id); assert(id < (int)es.size());int32_t from, idx; tie(from, idx) = es[id];auto const& e = g[from][idx];auto const& r = g[e.to][e.rev];return { from, e.to, r.cap, e.cap+r.cap, e.cost };}vector<edge_t> edges() const {vector<edge_t> ret(E);rep (id,E) ret[id] = edge(id);return ret;}template <class T> static constexpr bool chmin(T &x, T const& y) {return x > y ? (x = y, true) : false;};void BellmanFord(int s) {fill(h.begin(), h.end(), inf);h[s] = 0;bool update = false;rep (_,V-1) {update = false;rep (x,V) if (h[x] < inf) {rep (i,g[x].size()) {auto const& e = g[x][i];if (e.cap > EPS && chmin(h[e.to], h[x] + e.cost)) {pv[e.to] = x, pe[e.to] = i;update = true;}}}if (not update) break;}assert(not update); // todo: cancel negative loopsneg_edge = false;}void Dijkstra(int s) { // use old husing P = pair<Cost,int32_t>;priority_queue<P, vector<P>, greater<P>> q;vector<Cost> d(V, inf);d[s] = 0;q.emplace(0, s);while (q.size()) {int val, x; tie(val, x) = q.top(); q.pop();if (d[x] < val) continue;rep (i,g[x].size()) {auto const& e = g[x][i];if (e.cap > EPS && chmin(d[e.to], d[x] + e.cost+h[x]-h[e.to])) {pv[e.to] = x, pe[e.to] = i;q.emplace(d[e.to], e.to);}}}rep (x,V) if (d[x] < inf) h[x] += d[x];}bool calc_next(int s = -1, int t = -1) {if (t < 0) s = this-> s, t = this->t;if (neg_edge) BellmanFord(s); else Dijkstra(s);if (h[t] >= inf) {next_cap = 0, next_cost = inf;return false;}next_cap = numeric_limits<Flow>::max();for (int x = t; x != s; x = pv[x]) chmin(next_cap, g[pv[x]][pe[x]].cap);next_cost = h[t];return next_cap > EPS;}void add_flow(Flow flow, int s = -1, int t = -1) {if (t < 0) s = this-> s, t = this->t;for (int x = t; x != s; x = pv[x]) {auto &e = g[pv[x]][pe[x]];e.cap -= flow;g[x][e.rev].cap += flow;}}pair<Cost, bool> min_cost_flow(int s, int t, Flow flow) {this->s = s, this->t = t;Cost cost = 0;while (flow > EPS) {if (not calc_next()) return { cost, false };auto f = min(flow, next_cap);add_flow(f);flow -= f;cost += f * next_cost;}return { cost, true };}#ifdef LOCALfriend string to_s(MinCostFlow a) {string ret = "\n";ret += "V = " + to_s(a.V) + ", E = " + to_s(a.E) + "\n";ret += "s = " + to_s(a.s) + ", t = " + to_s(a.t) + "\n";for (auto const& p : a.es) {auto const& e = a.g[p.first][p.second];auto const& r = a.g[e.to][e.rev];ret += to_s(e.id) + " : ";ret += to_s(p.first) + "->" + to_s(e.to) + ", ";ret += "flow " + to_s(r.cap) + "/" + to_s(e.cap+r.cap) + ", ";ret += "cost " + to_s(e.cost) + "\n";}return ret;}#endif};// <<<int32_t main() {int n, m; cin >> n >> m;struct edge { int to, c, d; };MinCostFlow<int, int> g(n);rep (i,m) {int a, b, c, d; cin >> a >> b >> c >> d; --a, --b;g.add_edge(a, b, 1, c);g.add_edge(b, a, 1, c);g.add_edge(a, b, 1, d);g.add_edge(b, a, 1, d);}cout << g.min_cost_flow(0, n-1, 2).fst << endl;}