Submission #1091149

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091149		orcslop	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	198 ms	30920 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>
bool ckmin(int& a, int b){ return b < a ? a = b, true : false; }
bool ckmax(int& a, int b){ return b > a ? a = b, true : false; }

const int N = 1e5 + 5; 

int n, m; 
int v[4]; 
int d[4][N]; 
int dp[3][N]; 
bool vis[N]; 
vector<pii> adj[N]; 
vector<int> nadj[N], ts, rts; 
priority_queue<pii, vector<pii>, greater<pii>> pq; 

void dfs(int node){
	for(auto x : nadj[node]){
		if(!vis[x]){
			vis[x] = 1; 
			dfs(x); 
		}
	}
	ts.pb(node); 
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m; 
    for(int i = 0; i < 4; i++){
    	cin >> v[i]; 
    	v[i]--; 
    }
    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}); 
    }
    for(int i = 0; i < 4; i++){
    	fill(d[i], d[i] + n, 1e18); 
    	d[i][v[i]] = 0; 
    	pq.push({0, v[i]}); 
    	while(!pq.empty()){
    		pii curr = pq.top(); pq.pop(); 
    		if(d[i][curr.s] != curr.f) continue; 
    		for(auto x : adj[curr.s]){
    			if(d[i][x.s] > curr.f + x.f){
    				d[i][x.s] = curr.f + x.f; 
    				pq.push({d[i][x.s], x.s}); 
    			}
    		}
    	}
    }
    int best = d[0][v[1]]; 
    for(int i = 0; i < n; i++){
    	for(auto x : adj[i]){
    		if(d[0][i] + d[1][x.s] + x.f == best){
    			nadj[i].pb(x.s); 
    		}
    	}
    }
    //topsort
    dfs(v[0]); 
    reverse(all(ts)); 
    rts.resize(n); 
    for(int i = 0; i < sz(ts); i++){
    	rts[ts[i]] = i; 
    }
    // calculate dp[2][N]; 
    // ans will be dp[0][0] + dp[1][0]; 
    for(int i = sz(ts) - 1; i >= 0; i--){
    	dp[0][i] = d[2][ts[i]]; 
    	dp[1][i] = d[3][ts[i]]; 
    	dp[2][i] = dp[0][i] + dp[1][i]; 
    	for(auto x : nadj[ts[i]]){
    		ckmin(dp[2][i], dp[2][rts[x]]);
    		ckmin(dp[2][i], dp[0][i] + dp[1][rts[x]]); 
    		ckmin(dp[2][i], dp[1][i] + dp[0][rts[x]]); 
    	}
    	for(auto x : nadj[ts[i]]){
    		ckmin(dp[0][i], dp[0][rts[x]]); 
    		ckmin(dp[1][i], dp[1][rts[x]]); 
    	}
    }
    cout << min(d[2][v[3]], dp[2][0]) << '\n'; 
    return 0; 
}

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