Submission #1130519

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130519		am_aadvik	Olympic Bus (JOI20_ho_t4)	C++20	37 / 100	1095 ms	8440 KiB

ho_t4

#pragma GCC optimize("O3")
#pragma GCC optimize("Os")
#pragma unroll
#include <iostream>
#include<set>
#include<vector>
#define int long long
const int inf = 1e17;
using namespace std;

vector<vector<int>> g[205];
vector<int> d[205];
bool p1[50005] = { 0 }, pn[50005] = { 0 };
vector<vector<int>> edg;
vector<int> apsp(int s, int n) {
	set<pair<int, int>> q;
	vector<int> dist(n + 1, inf);
	q.insert({ 0, s }), dist[s] = 0;
	while (q.size()) {
		pair<int, int> f = *q.begin();
		q.erase(q.begin());
		for (auto y : g[f.second]) {
			int i = y[0], x = y[1];
			if (dist[i] > (x + f.first)) {
				if (dist[i] != inf) q.erase({ dist[i], i });
				dist[i] = (x + f.first);
				q.insert({ dist[i], i });
			}
		}
	}
	return dist;
}

vector<int> path(int s, int n, int t) {
	set<pair<int, int>> q;
	vector<int> dist(n + 1, inf), ans;
	vector<pair<int, int>> prv(n + 1, {-1, -1});
	q.insert({ 0, s }), dist[s] = 0;
	while (q.size()) {
		pair<int, int> f = *q.begin();
		q.erase(q.begin());
		if (f.second == t) break;
		for (auto y : g[f.second]) {
			int i = y[0], x = y[1];
			if (dist[i] > (x + f.first)) {
				if (dist[i] != inf) q.erase({ dist[i], i });
				dist[i] = (x + f.first);
				q.insert({ dist[i], i });
				prv[i] = { f.second, y[3] };
			}
		}
	}
	
	pair<int,int> cur = prv[t];
	while (cur.first != -1)
		ans.push_back(cur.second), cur = prv[cur.first];
	return ans;
}

int excl(int s, int n, int t, int e) {
	set<pair<int, int>> q;
	vector<int> dist(n + 1, inf);
	q.insert({ 0, s }), dist[s] = 0;
	while (q.size()) {
		pair<int, int> f = *q.begin();
		q.erase(q.begin());
		if (f.second == t) return f.first;
		for (auto y : g[f.second]) {
			if (y[3] == e) continue;
			int i = y[0],  x = y[1];
			if (dist[i] > (x + f.first)) {
				if (dist[i] != inf) q.erase({ dist[i], i });
				dist[i] = (x + f.first);
				q.insert({ dist[i], i });
			}
		}
	}
	return inf;
}

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);

	int n, m; cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int u, v, c, d; cin >> u >> v >> c >> d;
		g[u].push_back({ v, c, d, i });
		edg.push_back({ u, v, c, d, i });
	}

	for (int i = 1; i <= n; ++i) d[i] = apsp(i, n);

	if (d[1][n] != inf) {
		vector<int> pth = path(1, n, n);
		for (auto x : pth) p1[x] = 1;
	}
	if (d[n][1] != inf) {
		vector<int> pth = path(n, n, 1);
		for (auto x : pth) pn[x] = 1;
	}

	int ans = d[1][n] + d[n][1];
	for (auto x : edg) {
		int c1, c2;
		if (!p1[x[4]]) c1 = min(d[1][n], d[1][x[1]] + x[2] + d[x[0]][n]);
		else {
			g[x[1]].push_back({ x[0], x[2], x[3], inf });
			c1 = excl(1, n, n, x[4]);
			g[x[1]].pop_back();
		}

		if (!pn[x[4]]) c2 = min(d[n][1], d[n][x[1]] + x[2] + d[x[0]][1]);
		else {
			g[x[1]].push_back({ x[0], x[2], x[3], inf });
			c2 = excl(n, n, 1, x[4]);
			g[x[1]].pop_back();
		}
		ans = min(ans, c1 + c2 + x[3]);
	}

	cout << ((ans >= inf) ? -1 : ans);
}

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 0 / 63