Submission #1286335

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286335		juan_alejandro	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	228 ms	19784 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);
    p[s]=-1;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> pq;
    pq.push({0,s});
    vector<int> vis(n+1,1e18+1);
    vis[s]=0;
    while(!pq.empty())
    {
        auto [w,e]=pq.top();pq.pop();
        //cout<<w<<" "<<e<<endl;
        for(const auto &[ww,ee]:x[e])
        {
            //cout<<"adyacente a:"<<ee<<endl;
            if(ww+w<vis[ee])
            {
                vis[ee]=ww+w;
                p[ee]=e;
                pq.push({ww+w,ee});
            }
        }
    }
    int vv=t;
    int pv;
    while(p[vv]!=-1)
    {
        //cout<<vv<<" "<<p[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;
        //if(pv==vv)break;
        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;
        }
    }
    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