제출 #684948

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
684948		ethening	Olympic Bus (JOI20_ho_t4)	C++17	0 / 100	804 ms	2880 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];
 
void dijk(int source, vector<ll>& dist) {
	dist.assign(n + 5, INF);
	typedef pair<ll, int> pli;
	priority_queue<pli, vector<pli>, greater<pli>> Q;
	dist[source] = 0;
	Q.push({0, source});
	vector<int> arrEdge(n + 5, 0);
	while (!Q.empty()) {
		auto [curDist, cur]  = Q.top();
		Q.pop();
		if (dist[cur] != curDist) continue;
		for (auto eg: v[cur]) {
			if (curDist + E[eg].wcost < dist[E[eg].to]) {
				dist[E[eg].to] = curDist + E[eg].wcost;
				arrEdge[E[eg].to] = eg;
				Q.push({dist[E[eg].to], E[eg].to}); 
			}
		}
	}
	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);
	typedef pair<ll, int> pli;
	priority_queue<pli, vector<pli>, greater<pli>> Q;
	dist[dest] = 0;
	Q.push({0, dest});
	vector<int> arrEdge(n + 5, 0);
	while (!Q.empty()) {
		auto [curDist, cur] = Q.top();
		Q.pop();
		if (dist[cur] != curDist) continue;
		for (auto eg: v2[cur]) {
			if (curDist + E[eg].wcost < dist[E[eg].fr]) {
				dist[E[eg].fr] = curDist + E[eg].wcost;
				arrEdge[E[eg].fr] = eg;
				Q.push({dist[E[eg].fr], E[eg].fr}); 
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		if (arrEdge[i] != 0) {
			E[arrEdge[i]].crit = true;
		}
	}
}
 
vector<vector<int>> adj;
vector<vector<int>> adj2;
 
int get_edge(int a, int b, int swapEg) {
	int ret = -1;
	if (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 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);
	}
	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;
	// }
 
	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].scost + E[i].wcost + distton[E[i].fr]);
		ll tmp2 = min(distfrn[1], distfrn[E[i].to] + E[i].scost + E[i].wcost + distto1[E[i].fr]);
		ans = min(ans, tmp + tmp2);
	}
 
	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]);
			}
		}
	}
 
	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: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63