Submission

Score: 100

User: Neozaawwman1

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

Language: cpp

Time: 0.009 second

Submitted On: 2026-01-28 23:32:30

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;

int N, M;
vector<vector<int>> rail, road;

vector<ll> dijkstra(int start, vector<vector<int>>& g){
    vector<ll> dist(N+1, INF);
    priority_queue<pair<ll,int>> pq;

    dist[start] = 0;
    pq.push({0, start});

    while(!pq.empty()){
        ll w = -pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if(w > dist[u]) continue;

        for(int v : g[u]){
            ll cost = 10LL * abs(v - u);
            if(dist[v] > w + cost){
                dist[v] = w + cost;
                pq.push({-dist[v], v});
            }
        }
    }
    return dist;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;

    rail.assign(N+1, {});
    road.assign(N+1, {});
    vector<vector<bool>> hasRail(N+1, vector<bool>(N+1, false));

    for(int i=0;i<M;i++){
        int a,b; cin >> a >> b;
        rail[a].push_back(b);
        rail[b].push_back(a);
        hasRail[a][b] = hasRail[b][a] = true;
    }

    // สร้างถนน = คู่ที่ไม่มีราง
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            if(i==j) continue;
            if(!hasRail[i][j])
                road[i].push_back(j);
        }
    }

    auto distTrain = dijkstra(1, rail);
    auto distCar   = dijkstra(1, road);

    if(distTrain[N] == INF || distCar[N] == INF)
        cout << -1;
    else
        cout << max(distTrain[N], distCar[N]);

    return 0;
}