Submission

Score: 100

User: Quaoar

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

Language: cpp

Time: 0.010 second

Submitted On: 2026-03-05 10:26:23

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

int src = 1;

int dij(int n , int target , vector<pair<int , int>> adj[]){
    vector <int> dist(n + 1 , INT_MAX);
    priority_queue < pair<int , int> , vector<pair<int,int>> , greater<pair<int , int>>> pq;

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

    while(!pq.empty()){
        int currDist = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        if (currDist > dist[u]){
            continue;
        }

        for (auto smth : adj[u]){
            int v = smth.first;
            int distance = smth.second;

            if (dist[v] > dist[u] + distance){
                dist[v] = dist[u] + distance;
                pq.push({dist[v] , v});
            }
        }
    }
    return dist[target];
}



int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n , m;
    cin >> m >> n;
    vector <pair <int,int>> adjT[m + 1];
    vector <pair <int,int>> adjR[m + 1];
    bool hasTrain[m + 1][m + 1] = {};

    for (int i = 0 ; i < n ; i++){
        int u , v;
        cin >> u >> v;
        adjT[u].push_back({v , 10 * abs(v - u)});
        adjT[v].push_back({u , 10 * abs(v - u)});
        hasTrain[u][v] = true;
        hasTrain[v][u] = true;
    }

    for (int i = 1 ; i <= m ; i++){
        for (int j = i + 1 ; j <= m ; j++){
            if (!hasTrain[i][j]){
                adjR[i].push_back({j , 10 * abs(i - j)});
                adjR[j].push_back({i , 10 * abs(i - j)});


            }
        }
    }
    int minTrain = dij(m, m , adjT);
    int minCar = dij(m,m,adjR);
    if (minTrain == INT_MAX || minCar == INT_MAX){
        cout << -1;
    } else {
        cout << max(minTrain, minCar);
    }
    
    return 0;
}