Submission #1091054

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091054		orcslop	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	344 ms	22932 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define f first
#define s second
#define mkp make_pair
#define pii pair<int, int>

const int N = 1e5 + 5; 

int n, m, s, t, u, v; 
int ds[N], dt[N], du[N], dv[N], dc[N]; 
vector<pii> adj[N]; 
priority_queue<pii, vector<pii>, greater<pii>> pq; 

void calcDV(){
    fill(dv, dv + n, 1e18); 
    dv[v] = 0; 
    pq.push({0, v}); 
    while(!pq.empty()){
    	pii curr = pq.top(); pq.pop(); 
    	if(dv[curr.s] != curr.f) continue; 
    	for(auto x : adj[curr.s]){
    		if(dv[x.s] > curr.f + x.f){
    			dv[x.s] = curr.f + x.f; 
    			pq.push({dv[x.s], x.s}); 
    		}
    	}
    }
}

void calcDU(){
    fill(du, du + n, 1e18); du[u] = 0; 
    pq.push({0, u}); 
    while(!pq.empty()){
    	pii curr = pq.top(); pq.pop(); 
    	if(du[curr.s] != curr.f) continue; 
    	for(auto x : adj[curr.s]){
    		if(du[x.s] > curr.f + x.f){
    			du[x.s] = curr.f + x.f; 
    			pq.push({du[x.s], x.s}); 
    		}
    	}
    }
}

void calcDS(){
    fill(ds, ds + n, 1e18); 
    ds[s] = 0; 
    pq.push({0, s}); 
    while(!pq.empty()){
    	pii curr = pq.top(); pq.pop(); 
    	if(ds[curr.s] != curr.f) continue; 
    	for(auto x : adj[curr.s]){
    		if(ds[x.s] > curr.f + x.f){
    			ds[x.s] = curr.f + x.f; 
    			pq.push({ds[x.s], x.s}); 
    		}
    	}
    }
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> s >> t >> u >> v; 
    s--; t--; u--; v--; 
    for(int i = 0; i < m; i++){
    	int a, b, c; 
    	cin >> a >> b >> c; 
    	a--; b--; 
    	adj[a].pb({c, b}); 
    	adj[b].pb({c, a}); 
    }
    fill(dt, dt + n, 1e18); 
    fill(dc, dc + n, 1e18); 
    calcDV(); 
    calcDU(); 
    calcDS(); 
    int best = ds[t]; 
    dt[t] = 0; 
    pq.push({0, t}); 
    while(!pq.empty()){
    	pii curr = pq.top(); pq.pop(); 
    	if(dt[curr.s] != curr.f) continue; 
    	for(auto x : adj[curr.s]){
    		if(dt[x.s] > curr.f + x.f){
    			dt[x.s] = curr.f + x.f; 
    			pq.push({dt[x.s], x.s}); 
    		}
    		if(dt[x.s] == curr.f + x.f){
				if(dt[curr.s] + ds[x.s] + x.f == best){
					dc[x.s] = min({dc[x.s], du[x.s], dc[curr.s]}); 
				}
    		}
    	}
    }
    int ans = du[v]; 
    for(int i = 0; i < n; i++){
    	if(ds[i] + dt[i] == best){
    		ans = min(ans, dv[i] + dc[i]); 
    	}
    }
    ///// break
    fill(ds, ds + n, 1e18); 
    fill(dt, dt + n, 1e18); 
    fill(dc, dc + n, 1e18); 
    swap(u, v); 
    calcDU(); 
    calcDV(); 
    calcDS(); 
    dt[t] = 0; 
    pq.push({0, t}); 
    while(!pq.empty()){
    	pii curr = pq.top(); pq.pop(); 
    	if(dt[curr.s] != curr.f) continue; 
    	for(auto x : adj[curr.s]){
    		if(dt[x.s] > curr.f + x.f){
    			dt[x.s] = curr.f + x.f; 
    			pq.push({dt[x.s], x.s}); 
    		}
    		if(dt[x.s] == curr.f + x.f){
				if(dt[curr.s] + ds[x.s] + x.f == best){
					dc[x.s] = min({dc[x.s], du[x.s], dc[curr.s]}); 
				}
    		}
    	}
    }
    for(int i = 0; i < n; i++){
    	if(ds[i] + dt[i] == best){
    		ans = min(ans, dv[i] + dc[i]); 
    	}
    }
    cout << ans << '\n'; 
    return 0; 
}

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