Submission #2009215

---

Source Code Expand

#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
struct edge { int to, cost, last; long long adv; };
struct state { int pos; long long cost; };
bool operator<(const state& s1, const state& s2) { return s1.cost > s2.cost; }
int N, M, S, T, x; long long dr[25259]; vector<int> s[133333], w[133333]; vector<edge> g[25259];
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cin >> N >> M >> S >> T;
	for (int i = 0; i < M; i++) {
		cin >> x; s[i].resize(x); w[i].resize(x - 1);
		for (int j = 0; j < x; j++) cin >> s[i][j];
		for (int j = 0; j < x - 1; j++) cin >> w[i][j];
		long long cs1 = 0;
		for (int j = 0; j < x - 1; j++) {
			g[s[i][j + 1]].push_back(edge{ s[i][j], w[i][j], s[i][0], cs1 });
			cs1 += w[i][j];
		}
		long long cs2 = 0;
		for (int j = x - 2; j >= 0; j--) {
			g[s[i][j]].push_back(edge{ s[i][j + 1], w[i][j], s[i][x - 1], cs2 });
			cs2 += w[i][j];
		}
	}
	fill(dr, dr + N, 1LL << 60); dr[T] = 0;
	priority_queue<state> q1; q1.push(state{ T, 0 });
	while (!q1.empty()) {
		int u = q1.top().pos; q1.pop();
		for (edge e : g[u]) {
			long long nd = dr[u] + e.cost;
			if (dr[e.to] > nd) {
				dr[e.to] = nd;
				q1.push(state{ e.to, nd });
			}
		}
	}
	for (int i = 0; i < N; i++) {
		for (edge &e : g[i]) {
			e.adv += dr[e.last];
		}
	}
	int l = 0, r = 1000000009;
	while (r - l > 1) {
		int m = (l + r) >> 1;
		fill(dr, dr + N, 1LL << 60); dr[S] = 0;
		priority_queue<state> que; que.push(state{ S, 0 });
		while (!que.empty()) {
			int u = que.top().pos; que.pop();
			for (edge e : g[u]) {
				long long nd = dr[u] + e.cost;
				if (dr[e.to] > nd && nd + e.adv <= m) {
					dr[e.to] = nd;
					que.push(state{ e.to, nd });
				}
			}
		}
		if (dr[T] == 1LL << 60) l = m;
		else r = m;
	}
	cout << r << endl;
	return 0;
}

Submission Info

Judge Result