Submission #1253234

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253234		dhuyyyy	Commuter Pass (JOI18_commuter_pass)	C++20	31 / 100	255 ms	23060 KiB

commuter_pass

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

using ii = pair<int,int>;

const int N = 1e5+5;

int n,m,s,t,u,v,a,b,c,ans = 0;
int d[N][3],dp[N][3];
bool vis[N];
vector <ii> adj[N];
void D(int u,int type){
    priority_queue<ii,vector<ii>,greater<ii>> pq;
    pq.push({0,u});
    d[u][type] = 0;
    while (!pq.empty()){
        int u = pq.top().se;
        int kc = pq.top().fi;
        pq.pop();
        if (kc > d[u][type]) continue;
        for (ii it : adj[u]){
            int v = it.fi;
            int kcv = it.se;
            if (d[v][type] > d[u][type] + kcv){
                d[v][type] = d[u][type] + kcv;
                pq.push({d[v][type],v});
            }
        }
    }
}
void trace(int u){
    dp[u][0] = d[u][1];
    dp[u][1] = d[u][2];
    vis[u] = 1;
    for (ii it : adj[u]){
        int v = it.fi;
        int kcv = it.se;
        if (d[v][0] == d[u][0] - kcv){
            if (!vis[v]) trace(v);
            dp[u][0] = min(dp[u][0],dp[v][0]);
            dp[u][1] = min(dp[u][1],dp[v][1]);
        }
    }
    ans = min(ans,dp[u][0] + dp[u][1]);
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m >> s >> t >> u >> v;
    for (int i = 1; i <= m; i++){
        cin >> a >> b >> c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    memset(d,0x3f,sizeof d);
    D(s,0);
    D(u,1);
    D(v,2);
    ans = d[v][1];
    trace(t);
    cout << ans;
    return 0;
}

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