Submission #1130528

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130528		am_aadvik	Olympic Bus (JOI20_ho_t4)	C++20	100 / 100	795 ms	3292 KiB

ho_t4

#pragma GCC optimize("O3")
#pragma GCC optimize("Os")
#include <iostream>
#include<set>
#include<vector>
const int inf = 2e9;
using namespace std;

class edge {
public:
	int u, v, c, d, i;
	edge(int u, int v, int c, int d, int i) { this->u = u, this->v = v, this->c = c, this->d = d, this->i = i; }
};

vector<edge> g[205], edg;
int d[205][205];
bool p1[50005] = { 0 }, pn[50005] = { 0 };
set<pair<int, int>> q;
int dist[205];
vector<int> ans;
int n, m;
pair<int, int> f, cur;
pair<int, int> prv[205];

void apsp(int n) {
	for (int k = 1; k <= n; ++k)
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= n; ++j)
				if((d[i][k] != inf) && (d[k][j] != inf))
					d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

vector<int> path(int s, int t) {
	for (int i = 1; i <= n; ++i) dist[i] = inf;
	ans.clear();
	for (int i = 1; i <= n; ++i) prv[i] = { -1, -1 };
	q.insert({ 0, s }), dist[s] = 0;
	while (q.size()) {
		f = *q.begin();
		q.erase(q.begin());
		if (f.second == t) {
			q.clear();
			break;
		}
		for (auto y : g[f.second]) {
			int i = y.v, x = y.c;
			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.i };
			}
		}
	}

	cur = prv[t];
	while (cur.first != -1)
		ans.push_back(cur.second), cur = prv[cur.first];
	return ans;
}

int excl(int s, int t, int e) {
	for (int i = 1; i <= n; ++i) dist[i] = inf;
	q.insert({ 0, s }), dist[s] = 0;
	while (q.size()) {
		f = *q.begin();
		q.erase(q.begin());
		if (f.second == t) {
			q.clear();
			return f.first;
		}
		for (auto y : g[f.second]) {
			if (y.i == e) continue;
			int i = y.v, x = y.c;
			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);

	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j)
			d[i][j] = inf;
	for (int i = 1; i <= n; ++i) d[i][i] = 0;
	for (int i = 0; i < m; ++i) {
		int u, v, c, di; cin >> u >> v >> c >> di;
		edge ce(u, v, c, di, i);
		g[u].push_back(ce), edg.push_back(ce);
		d[u][v] = min(d[u][v], c);
	}
	apsp(n);

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

	int ans;
	if (max(d[1][n], d[n][1]) >= inf) ans = inf;
	else ans = d[1][n] + d[n][1];

	for (auto x : edg) {
		int c1, c2;
		if (!p1[x.i]) {
			int val;
			if (max(d[1][x.v], d[x.u][n]) >= inf) val = inf;
			else val = d[1][x.v] + x.c + d[x.u][n];
			c1 = min(d[1][n], val);
		}
		else {
			edge ce(x.v, x.u, x.c, x.d, inf);
			g[x.v].push_back(ce);
			c1 = excl(1, n, x.i);
			g[x.v].pop_back();
		}

		if (!pn[x.i]) {
			int val;
			if (max(d[n][x.v], d[x.u][1]) >= inf) val = inf;
			else val = d[n][x.v] + x.c + d[x.u][1];
			c2 = min(d[n][1], val);
		}
		else {
			edge ce(x.v, x.u, x.c, x.d, inf);
			g[x.v].push_back(ce);
			c2 = excl(n, 1, x.i);
			g[x.v].pop_back();
		}

		if(max(c1, c2) < inf)
			ans = min(ans, c1 + c2 + x.d);
	}
	cout << ((ans >= inf) ? -1 : ans);
}

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