Submission #1130337

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130337		am_aadvik	Olympic Bus (JOI20_ho_t4)	C++20	5 / 100	1103 ms	177940 KiB

ho_t4

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

vector<vector<int>> g[2][205];
vector<vector<long long>> dist[2]; //path, node, rev. edg
set<vector<long long>> q; //{dist+cost, node, path, rev. edg.}
vector<long long> f;

long long path(int s, int t, int n, int m) {
	dist[0].assign(n + 1, vector<long long>(m + 1, inf));
	dist[1].assign(n + 1, vector<long long>(m + 1, inf));

	q.insert({ 0, s, 0, 0 }), dist[0][s][0] = 0;
	while (q.size()) {
		f = *q.begin();
		q.erase(q.begin());
		if (f[2] && (f[1] == s)) { //complete!
			q.clear();
			return f[0];
		}

		if (f[1] == t) f[2] = 1; //1 way complete!
		for (auto x : g[0][f[1]]) { //out edgs.
			if (f[3] != x[3]) { //this edg. wasnt rev.
				long long val = dist[f[2]][x[0]][f[3]];
				if (val > (f[0] + x[1])) {
					if (val != inf)
						q.erase({ val, x[0], f[2], f[3] });
					dist[f[2]][x[0]][f[3]] = (f[0] + x[1]);
					q.insert({ (f[0] + x[1]), x[0], f[2], f[3] });
				}
			}
		}

		for (auto x : g[1][f[1]]) { //in edgs.
			if (f[3] == x[3]) { //this edge was rev.
				long long val = dist[f[2]][x[0]][f[3]];
				if (val > (f[0] + x[1])) {
					if (val != inf)
						q.erase({ val, x[0], f[2], f[3] });
					dist[f[2]][x[0]][f[3]] = (f[0] + x[1]);
					q.insert({ (f[0] + x[1]), x[0], f[2], f[3] });
				}
			}
			else if ((f[3] == 0) && (!f[2])) {
				f[3] = x[3];
				long long val = dist[f[2]][x[0]][f[3]];
				if (val > (f[0] + x[1] + x[2])) {
					if (val != inf)
						q.erase({ val, x[0], f[2], f[3] });
					dist[f[2]][x[0]][f[3]] = (f[0] + x[1] + x[2]);
					q.insert({ (f[0] + x[1] + x[2]), x[0], f[2], f[3] });
				}
				f[3] = 0;
			}
		}
	}
	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 = 1; i <= m; ++i) {
		int u, v, c, d; cin >> u >> v >> c >> d;
		g[0][u].push_back({ v, c ,d, i });
		g[1][v].push_back({ u, c, d, i });
	}

	long long ans = min(path(1, n, n, m), path(n, 1, n, m));
	cout << ((ans == inf) ? -1 : ans);
}

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