Submission

[PPPPPPPPPPPPPPPPPPPP]

Score: 100

User: devilpoohs

Problemset: รถยนต์ รถไฟ เรือเมล์ ลิเก ตำรวจ

Language: cpp

Time: 0.022 second

Submitted On: 2025-03-30 11:10:53

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m;
    cin>>n>>m;
    int u,v;
    vector<vector<pair<int,int>>> adjtrain(n+1);
    for(int i=0;i<m;i++){
        cin>>u>>v;
        adjtrain[u].emplace_back(v,abs(u-v)*10);
        adjtrain[v].emplace_back(u,abs(u-v)*10);
    }
    vector<vector<pair<int,int>>> adjcar(n+1);
    queue<int> q;
    q.emplace(1);
    vector<bool> visited(n+1,false);
    bool addcar[n+1];

    for(int i=1;i<=n;i++){
    memset(addcar,false,sizeof(addcar));        
        for(auto j:adjtrain[i]){
            addcar[j.first]=true;
        }
        for(int j=1;j<=n;j++){
            if(addcar[j]==false and i!=j){
                adjcar[i].emplace_back(j,abs(i-j)*10);
                // cout<<i<<':'<<j<<' ';
            }
        }
        // cout<<'\n';
    }
    vector<int> disttrain(n+1,-1);
    vector<int> distcar(n+1,-1);
    distcar[1]=0;
    disttrain[1]=0;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;//small first
    pq.emplace(0,1);
    vector<bool> visitedtrain(n+1,false);
    while(!pq.empty()){
        auto cur=pq.top();
        pq.pop();
        int curwt=cur.first;
        int curnode=cur.second;
        visitedtrain[curnode]=true;
        for(auto i:adjtrain[curnode]){
            int vnode=i.first;
            int vwt=i.second;
            if(!visitedtrain[vnode] and(disttrain[vnode]==-1 or vwt+curwt<disttrain[vnode])){
                disttrain[vnode]=vwt+curwt;
                pq.emplace(curwt+vwt,vnode);
            }
        
        }
    }
    pq.emplace(0,1);
    vector<bool> visitedcar(n+1,false);
    while(!pq.empty()){
        auto cur=pq.top();
        pq.pop();
        int curwt=cur.first;
        int curnode=cur.second;
        visitedcar[curnode]=true;
        for(auto i:adjcar[curnode]){
            int vnode=i.first;
            int vwt=i.second;
            if(!visitedcar[vnode] and(distcar[vnode]==-1 or vwt+curwt<distcar[vnode])){
                distcar[vnode]=vwt+curwt;
                pq.emplace(curwt+vwt,vnode);
            }
        }
    }
    // for(int i=1;i<=n;i++){
    //     cout<<distcar[i]<<' ';
    // }
    // cout<<'\n';
    // for(int i=1;i<=n;i++){
    //     cout<<disttrain[i]<<' ';
    // }
    if(distcar[n]==-1 or disttrain[n]==-1){
        cout<<-1;

    }else
    cout<<max(distcar[n],disttrain[n]);

    return 0;
}




/*
g++ 1.cpp -o 1.exe; if ($?) { .\1.exe }

5 3
1 3
3 4
4 5

4 6
1 2
1 3
1 4
2 3
2 4
3 4

5 5
4 2
3 5
4 5
5 1
1 2
*/