제출 #652600

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
652600		ymm	Olympic Bus (JOI20_ho_t4)	C++17	100 / 100	943 ms	3156 KiB

ho_t4

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

#define int ll
const int N = 256;
const int M = 50010;
vector<pii> A[N], T[N];
const int inf = 3e9+1000;
int w[M], p[M];
int dis0[N], disn[N], dis0T[N], disnT[N], disdard[N];
pii par[N];
pii edge[M];
bool is_path[M];
int n, m;

void dij(int s, int dis[], vector<pii> A[])
{
	fill(dis, dis+n, inf);
	fill(par, par+n, pii{-1, -1});
	dis[s] = 0;
	set<pii> st = {{0, s}};
	while (st.size()) {
		auto [d, v] = *st.begin();
		st.erase(st.begin());
		for (auto [u, e] : A[v]) {
			int w = ::w[e];
			if (d + w < dis[u]) {
				st.erase({dis[u], u});
				dis[u] = d+w;
				par[u] = {v, e};
				st.insert({dis[u], u});
			}
		}
	}
}

void input()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> m;
	Loop (e,0,m) {
		int v, u;
		cin >> v >> u >> w[e] >> p[e];
		--v; --u;
		A[v].push_back({u,e});
		T[u].push_back({v,e});
		edge[e] = {v, u};
	}
	Loop (i,0,n) {
		sort(A[i].begin(), A[i].end(), [](pii x, pii y){
			return w[x.second] < w[y.second];
		});
	}
}

signed main()
{
	input();
	int ans = 0;
	dij(0, dis0, A);
	dij(0, dis0T, T);
	ans += dis0[n-1];
	int v = n-1;
	for (;;) {
		auto [u, e] = par[v];
		if (u == -1)
			break;
		is_path[e] = 1;
		v = u;
	}
	dij(n-1, disn, A);
	dij(n-1, disnT, T);
	ans += disn[0];
	v = 0;
	for (;;) {
		auto [u, e] = par[v];
		if (u == -1)
			break;
		is_path[e] = 1;
		v = u;
	}
	Loop (e,0,m) {
		auto [v, u] = edge[e];
		if (is_path[e]) {
			int tmp = inf;
			swap(tmp, w[e]);
			w[m] = tmp;
			A[u].push_back({v,m});
			int x = p[e];
			dij(0, disdard, A);
			x += disdard[n-1];
			dij(n-1, disdard, A);
			x += disdard[0];
			ans = min(ans, x);
			A[u].pop_back();
			w[e] = tmp;
		} else {
			int x = dis0[u] + w[e] + disnT[v] + disn[0];
			int y = dis0[n-1] + disn[u] + w[e] + dis0T[v];
			int z =   dis0[u] + w[e] + disnT[v]
			        + disn[u] + w[e] + dis0T[v];
			ans = min(ans, p[e] + min({x, y, z}));
		}
	}
	cout << (ans >= inf? -1: ans) << '\n';
}

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