Submission #441002

#	Time	Username	Problem	Language	Result	Execution time	Memory
441002		ritul_kr_singh	Olympic Bus (JOI20_ho_t4)	C++17	100 / 100	364 ms	3524 KiB

ho_t4

// #pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define sp << ' ' <<
#define nl << '\n'
 
const int INF = 2e9+1;
 
int n, m, ans = INF;
vector<array<int, 3>> g[2][200];
 
inline int add(int x, int y, int z){
	if(max(x, max(y, z)) == INF) return INF;
	return x + y + z;
}
inline int add(int x, int y){
	if(max(x, y) == INF) return INF;
	return x + y;
}
 
void dijkstra(int r, int s, vector<int> &d, int i){
	d.assign(n, INF);
	bitset<200> vis; if(r>=0) vis[r] = 1;
	d[s] = 0;
	if(r == s) return;
	for(int _=0; _<n; ++_){
		array<int, 2> j = {INF, -1};
		for(int u=0; u<n; ++u) if(!vis[u] && d[u] < j[0]) j = {d[u], u};
		if(j[1] < 0 || j[1] == r) continue;
		vis[j[1]] = 1;
		for(auto &[v, w, t] : g[i][j[1]])
			if(v != r && !vis[v]) d[v] = min(d[v], add(j[0], w));
	}
}
 
signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	while(m--){
		int u, v, w, d; cin >> u >> v >> w >> d;
		--u, --v;
		g[0][u].push_back({v, w, d});
		g[1][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], 0);
			dijkstra(u, i ? n-1 : 0, e[i], 1);
		}
 
		for(auto &[v, w, x] : g[1][u])
			for(int j=0; j<2; ++j)
				d[j][u] = min(d[j][u], add(w, d[j][v]));
 
		array<int, 2> x[2], y[2];
		for(int j=0; j<2; ++j) x[j] = y[j] = {INF, -1};
 
		for(int i=0; i<(int)g[0][u].size(); ++i){
			for(int j=0; j<2; ++j){
				y[j] = min(y[j], {add(e[j][g[0][u][i][0]], g[0][u][i][1]), i});
				if(x[j] > y[j]) swap(x[j], y[j]);
			}
		}
		if(u == 0) x[0][0] = y[0][0] = 0;
		if(u==n-1) x[1][0] = y[1][0] = 0;
 
		for(int i=0; i<(int)g[0][u].size(); ++i){
			auto &[v, w, t] = g[0][u][i];
			array<int, 2> uE;
			for(int j=0; j<2; ++j) uE[j] = x[j][1] == i ? y[j][0] : x[j][0];
 
			int a = add(d[0][v], w, uE[1]);
			int b = add(d[1][v], w, uE[0]);
 
			ans = min(ans, add(a, t, min(e[0][n-1], add(d[1][u], uE[0]))));
			ans = min(ans, add(b, t, min(e[1][0], add(uE[1], d[0][u]))));
 
			ans = min(ans, add(a, b, t));
		}
	}
 
	vector<int> d[2];
	dijkstra(-1, 0, d[0], 0);
	dijkstra(-1, n-1, d[1], 0);
	ans = min(ans, add(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: 63 / 63