結果

問題 No.1301 Strange Graph Shortest Path
ユーザー otogawa
提出日時 2025-04-22 11:17:11
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,854 bytes
コンパイル時間 2,197 ms
コンパイル使用メモリ 205,940 KB
実行使用メモリ 40,188 KB
最終ジャッジ日時 2025-04-22 11:17:32
合計ジャッジ時間 19,281 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 32 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define int ll
#define fast_io cin.tie(0)->sync_with_stdio(0);
#define endl '\n'
typedef long long ll;

const int INF = 1e18;

struct MinCost {
	struct edge {
		int to, next, cap, cost;
	};
	int n;
	vector<int> first, prev, dist;
	vector<bool> in;
	vector<edge> g;

	MinCost(int _n) : n(_n), first(n, -1), prev(n), dist(n), in(n) {};

	void add(int u, int v, int c, int w) {
		int id = g.size();
		g.push_back({v, first[u], c, w});
		first[u] = id;
		g.push_back({u, first[v], 0, -w});
		first[v] = ++id;
	}

	bool spfa(int s, int t) {
		fill(dist.begin(), dist.end(), INF);
		dist[s] = 0, in[s] = 1;
		queue<int> q;
		q.push(s);
		while (!q.empty()) {
			int u = q.front();
			q.pop();
			in[u] = 0;
			for (int e = first[u]; ~e; e = g[e].next) {
				int v = g[e].to;
				int ndist = dist[u] + g[e].cost;
				if (g[e].cap > 0 && ndist < dist[v]) {
					dist[v] = ndist;
					prev[v] = e;
					if (!in[v]) {
						q.push(v);
						in[v] = 1;
					}
				}
			}
		}
		// return dist[t] < 0;
		return dist[t] < INF;
	}

	pair<int, int> max_flow(int s, int t) {
		int flow = 0, cost = 0;
		while (spfa(s, t)) {
			int cur = t, curf = INF;
			while (cur != s) {
				int e = prev[cur];
				curf = min(curf, g[e].cap);
				cur = g[e^1].to;
			}
			flow += curf;
			cost += dist[t] * curf;
			cur = t;
			while (cur != s) {
				int e = prev[cur];
				g[e].cap -= curf;
				g[e^1].cap += curf;
				cur = g[e^1].to;
			}
		}
		return {flow, cost};
	}
};


int32_t main() {
	fast_io;

    int n, m; cin >> n >> m;

    MinCost g(n + 1);
    g.add(n, 0, 2, 0);
    for (int i = 0; i < m; i++) {
        int u, v, w, t; cin >> u >> v >> w >> t; --u, --v;
        g.add(u, v, 1, w);
        g.add(v, u, 1, w);
        g.add(u, v, 1, t);
        g.add(v, u, 1, t);
    }
    cout << g.max_flow(n, n - 1).second << endl;
}
0