Submission #754393

#	Time	Username	Problem	Language	Result	Execution time	Memory
754393		penguin133	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	393 ms	27232 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int dist1[300005], dist2[300005], n, m, s, t, u, v;

vector <pi> adj[100005];
int brr[100005][4];
void dijk(int dist[], int ss){
	for(int i = 1; i <= n; i++)dist[i] = 1e18;
	dist[ss] = 0;
	priority_queue <pi, vector <pi>, greater<pi> > pq;
	pq.push({0, ss});
	while(!pq.empty()){
		int x = pq.top().fi, y = pq.top().se;
		pq.pop();
		if(dist[y] < x)continue;
		for(auto [i, j] : adj[y]){
			if(dist[i] > x + j)dist[i] = x + j, pq.push({dist[i], i});
		}
	}
}

void solve(){
	cin >> n >> m >> s >> t >> u >> v;
	while (m--){
		int a, b, c; cin >> a >> b >> c;
		adj[a].push_back({b, c});
		adj[b].push_back({a, c});
	}
	dijk(dist1, s);
	dijk(dist2, t);
	for(int i = 1; i <= n; i++)for(int j = 0; j < 4; j++)brr[i][j] = 1e18;
	brr[u][0] = brr[u][1] = brr[u][2] = brr[u][3] = 0;
	priority_queue <pii, vector<pii>, greater<pii> > pq;
	pq.push({0, {u, 0}});
	while(!pq.empty()){
		int x = pq.top().fi, y = pq.top().se.fi, z = pq.top().se.se;
		pq.pop();
		if(brr[y][z] < x)continue;
		for(auto [i, j] : adj[y]){
			if(z == 0){
				if(dist1[y] + dist2[i] + j == dist1[t]){
					if(brr[i][1] > x)brr[i][1] = x, pq.push({brr[i][1], {i, 1}});
				}
				else if(dist1[i] + dist2[y] + j == dist1[t]){
					if(brr[i][2] > x)brr[i][2] = x, pq.push({brr[i][2], {i, 2}});
				}
				if(brr[i][0] > x + j)brr[i][0] = x + j, pq.push({brr[i][0], {i, 0}});
			}
			else if(z == 1){
				if(dist1[y] + j + dist2[i] == dist1[t]){
					if(brr[i][1] > x)brr[i][1] = x, pq.push({brr[i][1], {i, 1}});
				}
				else{
					if(brr[i][3] > x + j)brr[i][3] = x + j, pq.push({brr[i][3], {i, 3}});
				}
			}
			else if(z == 2){
				if(dist1[i] + dist2[y] + j == dist1[t]){
					if(brr[i][2] > x)brr[i][2] = x, pq.push({brr[i][2], {i, 2}});
				}
				else{
					if(brr[i][3] > x + j)pq.push({x + j, {i, 3}}), brr[i][3] = x + j;
				}
			}
			else{
				if(brr[i][3] > x + j)brr[i][3] = x + j, pq.push({brr[i][3], {i, 3}});
			}
		}
	}
	cout << min({brr[v][0], brr[v][1], brr[v][2], brr[v][3]});
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message (stderr)

commuter_pass.cpp:83:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   83 | main(){
      | ^~~~

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45