Submission #833924

#	Time	Username	Problem	Language	Result	Execution time	Memory
833924		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	348 ms	30776 KiB

commuter_pass

#include<bits/stdc++.h>
#define fi first
#define se second
#define pli pair<long long,int>
using namespace std;

const int nmax=2e5+1;
const int mod=1e9+7;

long long dp[nmax],dq[nmax],kq[nmax];
vector<pli> g[nmax];
vector<int> vt1[nmax],vt2[nmax];
int n,m;
priority_queue<pli,vector<pli>,greater<pli>> pq;

void dijkstra(int b,long long c[],vector<pli> s[])
{
    pq.push({0,b});
    while(!pq.empty()){
        auto [p,u]=pq.top();
        pq.pop();
        if(p>c[u]) continue;
        for(auto [w,v]:s[u]){
            if(c[v]>p+w){
                c[v]=w+p;
                pq.push({c[v],v});
            }
        }
    }
}

void spdijkstra(int b,long long c[],vector<int> s[])
{
    for(int i=1;i<=n;i++)
        c[i]=1e18;
    c[b]=0;
    pq.push({0,b});
    while(!pq.empty()){
        auto [p,u]=pq.top();
        pq.pop();
        if(p>c[u]) continue;
        for(auto [w,v]:g[u]){
            if(c[v]>p+w){
                c[v]=w+p;
                pq.push({c[v],v});
            }
        }
        for(auto v:s[u]){
            if(c[v]>p){
                c[v]=p;
                pq.push({c[v],v});
            }
        }
    }
}

int x[nmax],y[nmax],w[nmax];

int main()
{
    int s,t,u,v;
    cin>>n>>m;
    cin>>s>>t;
    cin>>u>>v;
    for(int i=1;i<=m;i++){
        cin>>x[i]>>y[i]>>w[i];
        g[x[i]].push_back({w[i],y[i]});
        g[y[i]].push_back({w[i],x[i]});
    }

    for(int i=1;i<=n;i++)
        dp[i]=dq[i]=1e18;

    dp[s]=0;
    dijkstra(s,dp,g);
    dq[t]=0;
    dijkstra(t,dq,g);

    for(int i=1;i<=m;i++){
        if(dp[x[i]]+w[i]+dq[y[i]]==dp[t])
            vt1[x[i]].push_back(y[i]);
    }
    long long ans=1e18;
    spdijkstra(u,kq,vt1);
    ans=kq[v];
    spdijkstra(v,kq,vt1);
    ans=min(ans,kq[u]);
    cout<<ans;
}

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