Submission

[PPPPPPPPPPPPPPPPPPPP]

Score: 100

User: MiyaZaki1072

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

Language: cpp

Time: 0.012 second

Submitted On: 2025-04-15 16:30:36

#include <bits/stdc++.h>
using namespace std;
vector<int>adjt[500];//train track
vector<int>adjc[500];//car track
bool tt[500][500];
struct A{
    int v,w;
    bool operator<(const A&o)const{
        return w>o.w;
    }
};
int disc[500],dist[500],anst=2e9,ansc=2e9;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,m;cin>>n>>m;
    while(m--){
        int u,v;cin>>u>>v;
        adjt[u].push_back({v});
        adjt[v].push_back({u});
        tt[u][v]=tt[v][u]=1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(!tt[i][j])adjc[i].push_back(j);
        }
    }
    memset(dist,0x3f,sizeof dist);
    memset(disc,0x3f,sizeof disc);
    priority_queue<A>pq;
    pq.push({1,0});
    disc[1]=0;
    while(pq.size()){
        A u = pq.top();pq.pop();
        if(u.v == n){
            ansc=u.w;
            break;
        }
        if(disc[u.v] < u.w)continue;
        for(auto &x:adjc[u.v]){
            if(disc[x] > disc[u.v] + 10*abs(x-u.v)){
                disc[x] = disc[u.v] + 10*abs(x-u.v);
                pq.push({x,disc[x]});
            }
        }
    }
    while(pq.size())pq.pop();
    pq.push({1,0});
    dist[1]=0;
    while(pq.size()){
        A u = pq.top();pq.pop();
        if(u.v == n){
            anst=u.w;
            break;
        }
        if(dist[u.v] < u.w)continue;
        for(auto &x:adjt[u.v]){
            if(dist[x] > dist[u.v] + 10*abs(x-u.v)){
                dist[x] = dist[u.v] + 10*abs(x-u.v);
                pq.push({x,dist[x]});
            }
        }
    }
    int ans = max(ansc,anst);
    if(ans > 1e9)cout<<"-1";
    else cout<<ans;
}