Submission #440979

#	Time	Username	Problem	Language	Result	Execution time	Memory
440979		ritul_kr_singh	Olympic Bus (JOI20_ho_t4)	C++17	37 / 100	1091 ms	5696 KiB

ho_t4

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'

const int INF = 1e16;

int n, m, ans = INF;
priority_queue<array<int, 2>> q;

void dijkstra(int r, int s, vector<int> &d, vector<array<int, 3>> g[]){
	d.assign(n, INF);
	d[s] = 0;
	if(r == s) return;
	q.push({0, s});
	while(!q.empty()){
		int u = q.top()[1], dist = -q.top()[0]; q.pop();
		if(dist != d[u]) continue;
		for(auto &[v, w, x] : g[u])
			if(v != r && d[v] > dist + w)
				q.push({-(d[v] = dist + w), v});
	}
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	vector<array<int, 3>> g[n], h[n];
	while(m--){
		int u, v, w, d; cin >> u >> v >> w >> d;
		--u, --v;
		g[u].push_back({v, w, d});
		h[v].push_back({u, w, d});
	}

	for(int u=0; u<n; ++u){
		vector<int> d[2], e[2];
		for(int i=0; i<2; ++i){
			dijkstra(u, i ? n-1 : 0, d[i], g);
			dijkstra(u, i ? n-1 : 0, e[i], h);
		}

		for(auto &[v, w, x] : h[u])
			for(int j=0; j<2; ++j)
				d[j][u] = min(d[j][u], w + d[j][v]);

		array<int, 2> suf[g[u].size()+1], pre;
		for(int i=0; i<2; ++i) suf[g[u].size()][i] = pre[i] = INF;

		for(int i=g[u].size(); --i>=0; )
			for(int j=0; j<2; ++j)
				suf[i][j] = min(suf[i+1][j], e[j][g[u][i][0]] + g[u][i][1]);

		for(int i=0; i<(int)g[u].size(); ++i){
			auto &[v, w, x] = g[u][i];
			array<int, 2> uE = {min(pre[0], suf[i+1][0]), min(pre[1], suf[i+1][1])};
			if(u == 0) uE[0] = 0;
			if(u==n-1) uE[1] = 0;

			int a = d[0][v] + w + uE[1];
			int b = d[1][v] + w + uE[0];

			ans = min(ans, a + x + min(e[0][n-1], d[1][u] + uE[0]));
			ans = min(ans, b + x + min(e[1][0], uE[1] + d[0][u]));

			ans = min(ans, a + b + x);

			for(int j=0; j<2; ++j)
				pre[j] = min(pre[j], e[j][v] + w);
		}
	}

	vector<int> d[2];
	dijkstra(-1, 0, d[0], g);
	dijkstra(-1, n-1, d[1], g);
	ans = min(ans, d[0][n-1] + d[1][0]);

	cout << (ans == INF ? -1 : ans) nl;
}

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