Submission #1273761

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273761		quanw267	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	186 ms	23136 KiB

commuter_pass

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pii pair<long long,long long>
#define fast ios_base::sync_with_stdio(0), cin.tie(0);

using namespace std;

const ll N = 1e5+5;
const ll INF = 1e15;

ll n,m,A,B,C,D,ans;
ll d[N][3],dp[N][3];
bool vis[N];
vector<pii> g[N];

void path(ll u, ll type){
    priority_queue<pii,vector<pii>,greater<pii>> q;
    d[u][type] = 0;
    q.push({0,u});
    while(!q.empty()){
        auto [kc, u] = q.top(); q.pop();
        if(kc > d[u][type]) continue;
        for(auto [v,w] : g[u]){
            if(d[v][type] > d[u][type] + w){
                d[v][type] = d[u][type] + w;
                q.push({d[v][type], v});
            }
        }
    }
}

void trace(ll u){
    dp[u][1] = d[u][1];
    dp[u][2] = d[u][2];
    vis[u] = 1;
    for(auto [v,w] : g[u]){
        if(d[v][0] == d[u][0] - w){
            if(!vis[v]) trace(v);
            dp[u][1] = min(dp[u][1], dp[v][1]);
            dp[u][2] = min(dp[u][2], dp[v][2]);
        }
    }
    ans = min({ans, dp[u][1] + d[u][2], dp[u][2] + d[u][1]});
}

int main(){
    fast
    cin >> n >> m >> A >> B >> C >> D;
    for(ll i=1; i<=m; i++){
        ll u,v,w; cin >> u >> v >> w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    for(ll i=1; i<=n; i++)
        for(int t=0; t<3; t++)
            d[i][t] = INF;

    path(A,0);
    path(C,1);
    path(D,2);

    ans = d[D][1];
    trace(B);

    cout << ans;
    return 0;
}

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