Submission #286664

#	Time	Username	Problem	Language	Result	Execution time	Memory
286664		reymontada61	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	193 ms	6756 KiB

ho_t4

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

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

vector<pair<pair<int, int>, pair<int, int>>> eds; 
vector<pair<pair<int, int>, pair<int, int>>> adj[MXN]; 
int par[MXN];
int dist1n[MXM];
int distn1[MXM];
int dist[MXN];
bool onpath[MXM];
bool onpath2[MXM];
int apsp[MXN][MXN];

int block = -1;

int get_dist(int src, int dest, int blo) {
	block = blo;
	memset(onpath, 0, sizeof onpath);
	for (int i=1; i<=n; i++) {
		dist[i] = LLONG_MAX / 10;
		par[i] = -1;
	}
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> proc;
	proc.push({0, src});
	
	while (!proc.empty()) {
		pair<int, int> tr = proc.top();
		proc.pop();
		int no = tr.second;
		int di = tr.first;
		if (dist[no] < di) continue;
		dist[no] = di;
		
		for (auto x: adj[no]) {
			int ad = x.first.first;
			int ind = x.first.second;
			int we = x.second.first;
			if (ind == block) continue;
			if (dist[no] + we < dist[ad]) {
				dist[ad] = dist[no] + we;
				par[ad] = ind;
				proc.push({dist[ad], ad});
			}
		}
	}
	
	for (int i=1; i<=n; i++) {
		if (par[i] == -1) continue;
		onpath[par[i]] = true;
	}
	
	return dist[dest];
}

signed main() {

	cin >> n >> m;
	
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=n; j++) {
			apsp[i][j] = LLONG_MAX / 10;
			if (i == j) apsp[i][j] = 0;
		}
	}
	
	for (int i=0; i<m; i++) {
		int a, b, w, f;
		cin >> a >> b >> w >> f;
		eds.push_back({{a, b}, {w, f}});
		adj[a].push_back({{b, i}, {w, f}});
		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 cr = get_dist(1, n, -1);
	for (int i=0; i<m; i++) {
		onpath2[i] = onpath[i];
	}
	dist1n[m] = cr;
	for (int i=0; i<m; i++) {
		if (!onpath2[i]) {
			dist1n[i] = cr;
		}
		else {
			block = i;
			dist1n[i] = get_dist(1, n, i);
		}
	}
	
	cr = get_dist(n, 1, -1);
	for (int i=0; i<m; i++) {
		onpath2[i] = onpath[i];
	}
	distn1[m] = cr;
	for (int i=0; i<m; i++) {
		if (!onpath2[i]) {
			distn1[i] = cr;
		}
		else {
			block = i;
			distn1[i] = get_dist(n, 1, i);
		}
	}
	
	int mn = apsp[1][n] + apsp[n][1];
	for (int i=0; i<m; i++) {
		int a = eds[i].first.first, b = eds[i].first.second;
		int w = eds[i].second.first, f = eds[i].second.second;
		mn = min(mn, f + apsp[1][a] + w + apsp[b][n] + distn1[i]);
		mn = min(mn, f + apsp[1][b] + w + apsp[a][n] + distn1[i]);
		mn = min(mn, f + apsp[n][a] + w + apsp[b][1] + dist1n[i]);
		mn = min(mn, f + apsp[n][b] + w + apsp[a][1] + dist1n[i]);
	}
	
	if (mn >= LLONG_MAX / 10) cout << -1 << endl;
	else cout << mn << endl;

}

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