Submission

Score: 0

User: Chawin

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

Language: cpp

Time: 0.002 second

Submitted On: 2026-03-22 08:22:08

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
const int inf = 1e9+7;

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

    int n, m;
    cin >> n >> m;

    vector<vector<pair<int, int>>> adjT(n+1);
    vector<vector<bool>> rail(n+1, vector<bool>(n+1, false));
    for(int i = 0; i < m; i++){
        int x, y;
        cin >> x >> y;

        int w = 10 * abs(y-x);

        adjT[x].push_back({y, w});
        adjT[y].push_back({x, w});

        rail[x][y] = rail[y][x] = true;
    }

    vector<vector<pair<int, int>>> adjC(n+1);
    for(int u = 1; u <= n; u++){
        for(int v = 1; v <= n; v++){
            if(u == v) continue;

            if(!rail[u][v]){
                int w = 10 * abs(v-u);
                adjC[u].push_back({v, w});
            }
        }
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    vector<int> distT(n+1, inf);

    pq.push({0, 1});
    distT[1] = 0;

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

        if(d > distT[u]) continue;

        for(auto &x : adjT[u]){
            int v = x.first;
            int w = x.second;

            if(distT[u]+w < distT[v]){
                distT[v] = distT[u]+w;
                pq.push({distT[v], v});
            }
        }
    }

    vector<int> distC(n+1, inf);

    pq.push({0, 1});
    distC[1] = 0;

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

        if(d > distC[u]) continue;

        for(auto &x : adjC[u]){
            int v = x.first;
            int w = x.second;

            if(distC[u]+w < distC[v]){
                distC[v] = distC[u]+w;
                pq.push({distC[v], v});
            }
        }
    }

    int timeT = distT[n], timeC = distC[n]; 
    if(timeT == inf || timeC == inf) cout << -1;
    else cout << min(timeT, timeC);

    return 0;
}