Submission

Score: 100

User: Neozaawwman1

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

Language: cpp

Time: 0.025 second

Submitted On: 2026-02-03 21:43:36

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int ex = 405;
int N,M;
vector<list<pair<int,ll>>> rail(ex);
vector<list<pair<int,ll>>> road(ex);
vector<ll> dstrain(ex,INF);
vector<ll> dscar(ex,INF);
bool hasrail[ex][ex];
priority_queue<pair<ll,int>> pq;

void dijisktra(vector<list<pair<int,ll>>> &v, vector<ll> &dist){
    while(!pq.empty()){
        ll w = -pq.top().first;
        int u = pq.top().second;
        pq.pop();
        if(dist[u]<w)continue;
        dist[u]=w;
        for(auto xx:v[u]){
            ll ww = xx.second;
            int v = xx.first;
            if(dist[v]>dist[u]+ww){
                dist[v]=dist[u]+ww;
                pq.push({-dist[v],v});
            }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin>>N>>M;
    for(int i=0; i<M; i++){
        int a,b;cin>>a>>b;
        ll c = abs(a-b);
        rail[a].push_back({b,c});
        rail[b].push_back({a,c});
        hasrail[a][b]=1;
        hasrail[b][a]=1;
    }
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            if(hasrail[i][j])continue;
            if(i==j)continue;
            ll w = abs(i-j);
            road[i].push_back({j,w});
        }
    }
    dstrain[1]=0;
    dscar[1]=0;
    pq.push({0,1});
    dijisktra(rail,dstrain);
    pq.push({0,1});
    dijisktra(road,dscar);
    ll car = dscar[N];
    ll train = dstrain[N];
    if(car==INF || train==INF){
        cout<<-1;
    }else{
        cout<<max(car,train)*10;
    }
    
    return 0;
}