Submission #684956

#	Time	Username	Problem	Language	Result	Execution time	Memory
684956		ethening	Olympic Bus (JOI20_ho_t4)	C++17	100 / 100	776 ms	3456 KiB

ho_t4

#include "bits/stdc++.h"
#include <functional>
#include <queue>
#include <vector>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int MAXN = 200;
const int MAXM = 50000;

const ll INF = 1000'000'000'000'000ll;

int n, m;

struct edge {
	int fr, to;
	ll wcost;
	ll scost;
	bool crit;
};

edge E[MAXM + 5];
// vector<int> v[MAXN + 5], v2[MAXN + 5];

vector<vector<int>> adj;
vector<vector<int>> adj2;

int get_edge(int a, int b, int swapEg) {
	int ret = -1;
	if (swapEg != -1 && E[swapEg].fr == b && E[swapEg].to == a) {
		ret = swapEg;
	}
	if (adj[a][b] != -1 && adj[a][b] != swapEg) {
		if (ret == -1 || E[adj[a][b]].wcost < E[ret].wcost) {
			ret = adj[a][b];
		}
	}
	if (adj2[a][b] != -1 && adj2[a][b] != swapEg) {
		if (ret == -1 || E[adj2[a][b]].wcost < E[ret].wcost) {
			ret = adj2[a][b];
		}
	}
	return ret;
}

void dijk(int source, vector<ll>& dist) {
	dist.assign(n + 5, INF);
	vector<bool> vis(n + 5, false);
	typedef pair<ll, int> pli;
	priority_queue<pli, vector<pli>, greater<pli>> Q;
	dist[source] = 0;
	vector<int> arrEdge(n + 5, 0);
	for (int k = 1; k <= n; k++) {
		int a = -1;
		ll min = INF;
		for (int i = 1; i <= n; i++) {
			if (!vis[i] && dist[i] < min) {
				a = i;
				min = dist[i];
			}
		}
		if (a == -1) break;
		vis[a] = true;
		for (int b = 1; b <= n; b++) {
			int eg = get_edge(a, b, -1);
			if (eg == -1) continue;
			if (!vis[b] && dist[a] + E[eg].wcost < dist[b]) {
				dist[b] = dist[a] + E[eg].wcost;
				arrEdge[b] = eg;
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		if (arrEdge[i] != 0) {
			E[arrEdge[i]].crit = true;
		}
	}
}

void dijk2(int dest, vector<ll>& dist) {
	dist.assign(n + 5, INF);
	vector<bool> vis(n + 5, false);
	typedef pair<ll, int> pli;
	priority_queue<pli, vector<pli>, greater<pli>> Q;
	dist[dest] = 0;
	vector<int> arrEdge(n + 5, 0);
	for (int k = 1; k <= n; k++) {
		int a = -1;
		ll min = INF;
		for (int i = 1; i <= n; i++) {
			if (!vis[i] && dist[i] < min) {
				a = i;
				min = dist[i];
			}
		}
		if (a == -1) break;
		vis[a] = true;
		for (int b = 1; b <= n; b++) {
			int eg = get_edge(b, a, -1);
			if (eg == -1) continue;
			if (!vis[b] && dist[a] + E[eg].wcost < dist[b]) {
				dist[b] = dist[a] + E[eg].wcost;
				arrEdge[b] = eg;
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		if (arrEdge[i] != 0) {
			E[arrEdge[i]].crit = true;
		}
	}
}

void dijk3(int source, vector<ll>& dist, int swapEg) {
	dist.assign(n + 5, INF);
	vector<bool> vis(n + 5, false);
	typedef pair<ll, int> pli;
	priority_queue<pli, vector<pli>, greater<pli>> Q;
	dist[source] = 0;
	for (int k = 1; k <= n; k++) {
		int a = -1;
		ll min = INF;
		for (int i = 1; i <= n; i++) {
			if (!vis[i] && dist[i] < min) {
				a = i;
				min = dist[i];
			}
		}
		if (a == -1) break;
		vis[a] = true;
		for (int b = 1; b <= n; b++) {
			int eg = get_edge(a, b, swapEg);
			if (eg == -1) continue;
			if (!vis[b] && dist[a] + E[eg].wcost < dist[b]) {
				dist[b] = dist[a] + E[eg].wcost;
			}
		}
	}
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		cin >> E[i].fr >> E[i].to >> E[i].wcost >> E[i].scost;
		E[i].crit = false;
		// v[E[i].fr].push_back(i);
		// v2[E[i].to].push_back(i);
	}

	adj.assign(n + 5, vector<int>(n + 5, -1));
	adj2.assign(n + 5, vector<int>(n + 5, -1));

	for (int i = 1; i <= m; i++) {
		if (adj[E[i].fr][E[i].to] == -1) {
			adj[E[i].fr][E[i].to] = i;
			continue;
		}
		if (adj2[E[i].fr][E[i].to] == -1) {
			adj2[E[i].fr][E[i].to] = i;
			if (E[adj2[E[i].fr][E[i].to]].wcost < E[adj[E[i].fr][E[i].to]].wcost) {
				swap(adj[E[i].fr][E[i].to], adj2[E[i].fr][E[i].to]);
			}
			continue;
		}
		if (E[i].wcost < E[adj2[E[i].fr][E[i].to]].wcost) {
			adj2[E[i].fr][E[i].to] = i;
			if (E[adj2[E[i].fr][E[i].to]].wcost < E[adj[E[i].fr][E[i].to]].wcost) {
				swap(adj[E[i].fr][E[i].to], adj2[E[i].fr][E[i].to]);
			}
		}
	}

	vector<ll> distfr1, distton, distfrn, distto1;
	dijk(1, distfr1);
	dijk(n, distfrn);
	dijk2(1, distto1);
	dijk2(n, distton);

	// cout << "!!!" << endl;
	// for (int i = 1; i <= n; i++) {
	// 	cout << i << " " << distfr1[i] << endl;
	// }
	// cout << "!!!" << endl;
	// for (int i = 1; i <= n; i++) {
	// 	cout << i << " " << distfrn[i] << endl;
	// }
	// cout << "!!!" << endl;
	// for (int i = 1; i <= n; i++) {
	// 	cout << i << " " << distto1[i] << endl;
	// }
	// cout << "!!!" << endl;
	// for (int i = 1; i <= n; i++) {
	// 	cout << i << " " << distton[i] << endl;
	// }
	// cout << "!!!" << endl;

	ll ans = INF;
	ans = min(ans, distfr1[n] + distfrn[1]);

	for (int i = 1; i <= m; i++) {
		if (E[i].crit) continue;
		ll tmp = min(distfr1[n], distfr1[E[i].to] + E[i].wcost + distton[E[i].fr]);
		ll tmp2 = min(distfrn[1], distfrn[E[i].to] + E[i].wcost + distto1[E[i].fr]);
		// cout << i << " " <<  tmp + tmp2 << "\n";
		ans = min(ans, tmp + tmp2 + E[i].scost);
	}
	// cout << ans << endl;

	for (int i = 1; i <= m; i++) {
		if (!E[i].crit) continue;
		vector<ll> dist2fr1(n + 5, INF), dist2frn(n + 5, INF);
		dijk3(1, dist2fr1, i);
		dijk3(n, dist2frn, i);
		ans = min(ans, dist2fr1[n] + dist2frn[1] + E[i].scost);
	}
	if (ans == INF) ans = -1;
	cout << ans << endl;
}

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