Submission #718081

#	Time	Username	Problem	Language	Result	Execution time	Memory
718081		esomer	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	402 ms	23488 KiB

commuter_pass

#include<bits/stdc++.h>
 
using namespace std;
 
#define endl "\n"

typedef long long int ll;

const int MOD = 1e9 + 7;

void Dijkstra(vector<vector<pair<int, ll>>>& adj, vector<ll>& dist, int initial){
	int n = (int)adj.size();
	vector<bool> vis(n, 0);
	dist[initial] = 0;
	priority_queue<pair<ll, int>> pq;
	pq.push({0, initial});
	while(!pq.empty()){
		int x = pq.top().second; pq.pop();
		if(vis[x]) continue;
		vis[x] = 1;
		for(auto p : adj[x]){
			int node = p.first; ll w = p.second;
			if(dist[node] > dist[x] + w){
				dist[node] = dist[x] + w;
				pq.push({-dist[node], node});
			}
		}
	}
}

void solve(){
	int n, m, s, t, u, v; cin >> n >> m >> s >> t >> u >> v; s--; t--; u--; v--;
	vector<vector<pair<int, ll>>> adj(n);
	for(int i = 0; i < m; i++){
		int a, b, c; cin >> a >> b >> c; a--; b--;
		adj[a].push_back({b, c});
		adj[b].push_back({a, c});
	}
	vector<ll> distv(n, 1e18);
	Dijkstra(adj, distv, v);
	vector<ll> distu(n, 1e18);
	Dijkstra(adj, distu, u);
	vector<ll> distt(n, 1e18);
	Dijkstra(adj, distt, t);
	vector<ll> dists(n, 1e18);
	Dijkstra(adj, dists, s);
	ll ans = distv[u];
	//Now I should make two more Dijkstras, one with minimum time to u, and the other with minimum time to v.
	
	priority_queue<pair<ll, int>> pq;
	vector<ll> mn(n, 1e18);
	vector<bool> vis(n, 0);
	for(int i = 0; i < n; i++){
		if(distt[i] + dists[i] == distt[s]){
			mn[i] = distu[i];
			pq.push({-mn[i], i});
		}
	}
	while(!pq.empty()){
		int x = pq.top().second; pq.pop();
		if(vis[x]) continue;
		ans = min(ans, mn[x] + distv[x]);
		vis[x] = 1;
		for(auto p : adj[x]){
			int node = p.first; ll w = p.second;
			if(dists[node] + distt[x] + w == distt[s] && mn[node] > mn[x]){
				mn[node] = mn[x];
				pq.push({-mn[node], node});
			}
		}
	}
	mn.assign(n, 1e18);
	vis.assign(n, 0);
	for(int i = 0; i < n; i++){
		if(distt[i] + dists[i] == distt[s]){
			mn[i] = distv[i];
			pq.push({-mn[i], i});
		}
	}
	while(!pq.empty()){
		int x = pq.top().second; pq.pop();
		if(vis[x]) continue;
		ans = min(ans, mn[x] + distu[x]);
		vis[x] = 1;
		for(auto p : adj[x]){
			int node = p.first; ll w = p.second;
			if(dists[node] + distt[x] + w == distt[s] && mn[node] > mn[x]){
				mn[node] = mn[x];
				pq.push({-mn[node], node});
			}
		}
	}
	cout << ans << endl;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
	//~ int tt; cin >> tt;
	int tt = 1;
	for(int t = 1; t <= tt; t++){
		solve();
	}
}

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