Submission #1286331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286331		juan_alejandro	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	151 ms	19276 KiB

commuter_pass

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout.precision(0);
    cout<<fixed;
    int n,m;
    cin>>n>>m;
    vector<pair<int,int>> x[n+1];
    int s,t;
    cin>>s>>t;
    int u,v;
    cin>>u>>v;
    for (int i = 0; i < m; i++)
    {
        int uu,vv,w;
        cin>>uu>>vv>>w;
        x[uu].push_back({w,vv});
        x[vv].push_back({w,uu});
    }
    queue<int> q;
    q.push(s);
    vector<int> p(n+1);
    vector<bool> vis(n+1,false);
    vis[s]=true;
    p[s]=-1;
    while(!q.empty())
    {
        int vv=q.front();
        q.pop();
        if(vv==t)break;
        for(const auto &[w,e]:x[vv])
        {
            if(!vis[e])
            {
                p[e]=vv;
                vis[e]=true;
                q.push(e);
            }
        }
    }
    int vv=t;
    int pv;
    while(p[vv]!=-1)
    {
        //cout<<vv<<endl;
        for( auto &[w,e]:x[vv])
        {
            if(e==p[vv]){w=0;/*cout<<"from "<<vv<<" to "<<e<<" now is free!"<<endl;*/break;}
        }
        if(vv!=t)
        for(auto&[w,e]:x[vv])
        if(e==pv){w=0;/*cout<<"from "<<vv<<" to "<<e<<" now is free!"<<endl;*/break;}
        pv=vv;
        vv=p[vv];
        if(p[vv]==-1)
        for(auto&[w,e]:x[vv])
        if(e==pv){w=0;/*cout<<"from "<<vv<<" to "<<e<<" now is free!"<<endl;*/break;}
    }
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> pq;
    pq.push({0,u});
    vector<int> vvis(n+1,1e9+1);
    while(!pq.empty())
    {
        auto [w,e]=pq.top();pq.pop();
        //cout<<"e:"<<e<<" with:"<<w<<endl;
        if(vvis[e]<=w)continue;
        vvis[e]=w;
        for(const auto &[ww,ee]:x[e])
        {
            //cout<<"adyacente a:"<<ee<<endl;
            pq.push({ww+w,ee});
        }
    }
    cout<<vvis[v]<<endl;
    return 0;
}

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