Submission #445143

#	Time	Username	Problem	Language	Result	Execution time	Memory
445143		ak2006	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	910 ms	46136 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
const ll mod = 1e9 + 7,inf = 1e18;
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
void setIO()
{
    fast;
}
int n = 1e5 + 5,m = 2e5 + 5,S,T,U,V;
vvvl adj(n);
vl distU(n,inf),distV(n,inf),distS(n,inf),distT(n,inf);
vvl dp(n,vl(2,inf));
int main()
{
    setIO();
    cin>>n>>m>>S>>T>>U>>V;
    while (m--){
        int u,v,w;
        cin>>u>>v>>w;
        adj[u].pb({v,w}),adj[v].pb({u,w});
    }
    priority_queue<pair<ll,int>>pq;
    distU[U] = 0;
    distV[V] = 0;
    distS[S] = 0;
    distT[T] = 0;

    pq.push({0,V});
    while (!pq.empty()){
        int cur = pq.top().second;
        if (distV[cur] != -pq.top().first){pq.pop();continue;}
        pq.pop();
        for (auto val:adj[cur]){
            int x = val[0];
            ll wt = val[1];
            if (distV[x] > distV[cur] + wt){
                distV[x] = distV[cur] + wt;
                pq.push({-distV[x],x});
            }
        }
    }

    pq.push({0,U});
    while (!pq.empty()){
        int cur = pq.top().second;
        if (distU[cur] != -pq.top().first){pq.pop();continue;}
        pq.pop();
        for (auto val:adj[cur]){
            int x = val[0];
            ll wt = val[1];
            if (distU[x] > distU[cur] + wt){
                distU[x] = distU[cur] + wt;
                pq.push({-distU[x],x});
            }
        }
    }

    pq.push({0,S});
    while (!pq.empty()){
        int cur = pq.top().second;
        if (distS[cur] != -pq.top().first){pq.pop();continue;}
        pq.pop();
        for (auto val:adj[cur]){
            int x = val[0];
            ll wt = val[1];
            if (distS[x] > distS[cur] + wt){
                distS[x] = distS[cur] + wt;
                pq.push({-distS[x],x});
            }
        }
    }

    pq.push({0,T});
    while (!pq.empty()){
        int cur = pq.top().second;
        if (distT[cur] != -pq.top().first){pq.pop();continue;}
        pq.pop();
        for (auto val:adj[cur]){
            int x = val[0];
            ll wt = val[1];
            if (distT[x] > distT[cur] + wt){
                distT[x] = distT[cur] + wt;
                pq.push({-distT[x],x});
            }
        }
    }

    vvl all;
    
    for (int i = 1;i<=n;i++)
        if (distS[i] + distT[i] == distS[T])all.pb({distS[i],i});
    sort(all.begin(),all.end());
    
    ll ans = distU[V];
    
    for (auto val:all){
        int x = val[1];
        dp[x][0] = min(dp[x][0],distU[x]);
        dp[x][1] = min(dp[x][1],distV[x]);
        for (auto val:adj[x]){
            int y = val[0];
            dp[y][0] = min(dp[y][0],dp[x][0]);
            dp[y][1] = min(dp[y][1],dp[x][1]);
        }
        ans = min(ans,dp[x][0] + distV[x]);
        ans = min(ans,dp[x][1] + distU[x]);
    }

    cout<<ans<<'\n';
    return 0;
}

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