Submission #287334

#	Time	Username	Problem	Language	Result	Execution time	Memory
287334		reymontada61	Olympic Bus (JOI20_ho_t4)	C++14	100 / 100	466 ms	4216 KiB

ho_t4

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

#define int long long
int n, m;
const int MXN = 205, MXM = 50005;

int apsp[MXN][MXN];
int eds[MXM][4];

vector<int> adj[MXN];
int mxh = INT_MAX * 1000ll;

int dist(int src, int dest, int skip) {
	int dists[MXN];
	for (int i=0; i<MXN; i++) dists[i] = mxh;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> proc;
	proc.push({0, src});
	while (!proc.empty()) {
		auto x = proc.top(); proc.pop();
		int di = x.first, no = x.second;
		if (dists[no] < di) continue;
		dists[no] = di;
		for (auto ed: adj[no]) {
			if (ed != skip) {
				int ot = eds[ed][0] + eds[ed][1] - no;
				int we = eds[ed][2];
				if (dists[ot] > dists[no] + we) {
					dists[ot] = dists[no] + we;
					proc.push({dists[ot], ot});
				}
			}
		}
		if (no == eds[skip][1]) {
			int ot = eds[skip][0];
			int od = dists[no] + eds[skip][2];
			if (dists[ot] > od) {
				dists[ot] = od;
				proc.push({od, ot});
			}
		}
	}
	return dists[dest];
} 

signed main() {
	
	for (int i=0; i<MXN; i++) {
		for (int j=0; j<MXN; j++) {
			apsp[i][j] = mxh;
		}
		apsp[i][i] = 0;
	}
	
	cin >> n >> m;
	for (int i=0; i<m; i++) {
		int a, b, w, c;
		cin >> a >> b >> w >> c;
		eds[i][0] = a;
		eds[i][1] = b;
		eds[i][2] = w;
		eds[i][3] = c;
		adj[a].push_back(i);
		apsp[a][b] = min(apsp[a][b], w);
	}
	
	for (int k=1; k<=n; k++) {
		for (int i=1; i<=n; i++) {
			for (int j=1; j<=n; j++) {
				if (apsp[i][k] + apsp[k][j] < apsp[i][j]) {
					apsp[i][j] = apsp[i][k] + apsp[k][j];
				}
			}
		}
	}
	
	int res = apsp[1][n] + apsp[n][1];
	for (int i=0; i<m; i++) {
		int a = eds[i][0], b = eds[i][1];
		int w = eds[i][2], c = eds[i][3];
		int d1 = min(apsp[1][n], apsp[1][b] + w + apsp[a][n]);
		int d2 = min(apsp[n][1], apsp[n][b] + w + apsp[a][1]);
		if (d1 + c + d2 < res) {
			int actual = dist(1, n, i) + dist(n, 1, i) + c;
			res = min(res, actual);
		}
	}
	
	if (res >= mxh) cout << -1 << endl;
	else cout << res << endl;
	
}

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