結果

問題 No.1301 Strange Graph Shortest Path
コンテスト
ユーザー ZOI-dayo
提出日時 2025-11-13 08:58:40
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 341 ms / 3,000 ms
コード長 3,186 bytes
コンパイル時間 5,162 ms
コンパイル使用メモリ 316,604 KB
実行使用メモリ 58,240 KB
最終ジャッジ日時 2025-11-13 08:58:59
合計ジャッジ時間 16,027 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

//@yukicoder 1301

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
using vl = vector<ll>;
template <class T>
using vec = vector<T>;
template <class T>
using vv = vec<vec<T>>;
template <class T>
using vvv = vv<vec<T>>;
template <class T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
#define rep(i, r) for (ll i = 0; i < (r); i++)
#define reps(i, l, r) for (ll i = (l); i < (r); i++)
#define rrep(i, l, r) for (ll i = (r)-1; i >= l; i--)
#define all(a) (a).begin(), (a).end()
#define sz(a) (ll)(a).size()
template <typename T>
bool chmax(T& a, const T& b) {
  return a < b ? a = b, true : false;
}
template <typename T>
bool chmin(T& a, const T& b) {
  return a > b ? a = b, true : false;
}
#include <bits/extc++.h>

const ll INF = 1e18;

struct MinCostFlow {
  struct Edge {
    ll from, to, rev, cap, cost, flow;
  };
  ll n;
  vv<Edge> ed;
  vl seen;
  vl dist, pi;
  vec<Edge*> par;
  MinCostFlow(ll n) : n(n), ed(n), seen(n), dist(n), pi(n), par(n) {}
  void add_edge(ll from, ll to, ll cap, ll cost) {
    if (from == to) return;
    ed[from].push_back(Edge{from, to, sz(ed[to]), cap, cost, 0});
    ed[to].push_back(Edge{to, from, sz(ed[from]) - 1, 0, -cost, 0});
  }
  void path(ll s) {
    fill(all(seen), 0);
    fill(all(dist), INF);
    dist[s] = 0;
    ll di;
    using Pq = __gnu_pbds::priority_queue<pll>;
    Pq q;
    vec<Pq::point_iterator> its(n);
    q.push({0, s});
    while (!q.empty()) {
      s = q.top().second;
      q.pop();
      seen[s] = 1;
      di = dist[s] + pi[s];
      for (Edge& e : ed[s])
        if (!seen[e.to]) {
          ll val = di - pi[e.to] + e.cost;
          if (e.cap - e.flow > 0 && val < dist[e.to]) {
            dist[e.to] = val;
            par[e.to] = &e;
            if (its[e.to] == q.end()) its[e.to] = q.push({-dist[e.to], e.to});
            else q.modify(its[e.to], {-dist[e.to], e.to});
          }
        }
    }
    rep(i, n) pi[i] = min(pi[i] + dist[i], INF);
  }
  pll maxflow(ll s, ll t, ll f = INF) {
    ll totflow = 0, totcost = 0;
    while (path(s), totflow < f && seen[t]) {
      ll fl_path = INF;
      for (Edge* x = par[t]; x; x = par[x->from])
        fl_path = min(fl_path, x->cap - x->flow);
      ll fl = min(fl_path, f - totflow);
      totflow += fl;
      for (Edge* x = par[t]; x; x = par[x->from]) {
        x->flow += fl;
        ed[x->to][x->rev].flow -= fl;
      }
    }
    rep(i, n) for (Edge& e : ed[i]) totcost += e.cost * e.flow;
    return {totflow, totcost / 2};
  }
  void setpi(ll s) {
    fill(all(pi), INF);
    pi[s] = 0;
    ll it = n, ch = 1;
    ll v;
    while (ch-- && it--)
      rep(i, n) if (pi[i] != INF) for (Edge& e : ed[i]) if (e.cap) if ((v = pi[i] + e.cost) < pi[e.to]) pi[e.to] = v, ch = 1;
    assert(it >= 0);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  ll n, m;
  cin >> n >> m;

  MinCostFlow mcf(n);

  rep(i, m) {
    ll u, v, c, d;
    cin >> u >> v >> c >> d;
    u--, v--;
    mcf.add_edge(u, v, 1, c);
    mcf.add_edge(v, u, 1, c);
    mcf.add_edge(u, v, 1, d);
    mcf.add_edge(v, u, 1, d);
  }

  cout << mcf.maxflow(0, n-1, 2).second << endl;
}
0