Submission #1167591

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167591		mareksb	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	75 ms	10560 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;
const int N=100005;
vector<pair<int,int>> mas[N];
int dS[N];
int dT[N];
int dV[N];
int dU[N];
int n,m;
int s,t;//commuter pass
int u,v;
void dijkstra(int start, int* dist){
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    dist[start]=0;
    pq.push({0,start});
    while(!pq.empty()){
        int x=pq.top().second;
        pq.pop();

        for(auto p:mas[x]){
            if(dist[x]+p.second<dist[p.first]){
                dist[p.first]=dist[x]+p.second;
                pq.push({dist[p.first],p.first});
            }
        }
    }
}
void dijkstra2(int start, int* dist){
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    dist[start]=0;
    pq.push({0,start});
    while(!pq.empty()){
        int x=pq.top().second;
        pq.pop();

        for(auto p:mas[x]){
            int cost=p.second;
            if(dS[x]+dT[x]==dS[t]&&dS[p.first]+dT[p.first]==dS[t]){
                cost=0;
            }
            if(dist[x]+cost<dist[p.first]){
                dist[p.first]=dist[x]+cost;
                pq.push({dist[p.first],p.first});
            }
        }
    }
}
void solve(){
    cin>>n>>m;
    for(int i=0;i<=n;i++){
        dS[i]=N;
        dT[i]=N;
        dV[i]=N;
        dU[i]=N;
    }
    cin>>s>>t;
    cin>>u>>v;

    for(int i=0;i<m;i++){
        int x,y,c;
        cin>>x>>y>>c;
        mas[x].push_back({y,c});
        mas[y].push_back({x,c});
    }
    dijkstra(s,dS);
    dijkstra(t,dT);
    dijkstra2(v,dV);
    dijkstra2(u,dU);
    int ans=INT_MAX;
    for(int i=1;i<=n;i++){
        //cout<<"i: "<<i<<' '<<dS[i]<<' '<<dT[i]<<'\n';
        if(dS[i]+dT[i]==dS[t]){
            ans=min(ans,dV[i]+dU[i]);
        }
    }
    cout<<ans<<'\n';
}

int main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

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