Submission

[PPPPPPPPPPPPPPPPPPPP]

Score: 100

User: devilpoohs

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

Language: cpp

Time: 0.013 second

Submitted On: 2025-03-30 11:17:40

//who copy this is gay 
#include<bits/stdc++.h>
using namespace std;
int curwt,curnode,vnode,vwt;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m,u,v;
    cin>>n>>m;
    vector<vector<pair<int,int>>> adjtrain(n+1);
    vector<vector<pair<int,int>>> adjcar(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);
    }
    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);
            }
        }
    }
    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;
    pq.emplace(0,1);
    vector<bool> visitedtrain(n+1,false);
    while(!pq.empty()){
        auto cur=pq.top();
        pq.pop();
        curwt=cur.first;
        curnode=cur.second;
        visitedtrain[curnode]=true;
        for(auto i:adjtrain[curnode]){
            vnode=i.first;
            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();
        curwt=cur.first;
        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);
            }
        }
    }
    if(distcar[n]==-1 or disttrain[n]==-1){
        cout<<-1;
    }else cout<<max(distcar[n],disttrain[n]);
    return 0;
}