Submission #833780

#	Time	Username	Problem	Language	Result	Execution time	Memory
833780		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	337 ms	36772 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],vt[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});
            }
        }
    }
}

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]=kq[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])
            w[i]=0;
        vt[x[i]].push_back({w[i],y[i]});
        vt[y[i]].push_back({w[i],x[i]});
    }
    dijkstra(u,kq,vt);
    cout<<kq[v];
}

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