Submission

Score: 100

User: Quaoar

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

Language: cpp

Time: 0.028 second

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

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

int src = 1;
int re(int m , int k , vector <pair <int,int>> adj[]){
    vector <int> dist(m + 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[k];
}

int main(){
    int n , k;
    cin >> k >> n;

    vector <pair <int,int>> adjt[k + 1];
    vector <pair <int,int>> adjc[k + 1];
    for (int i = 0 ; i < n ; i++){
        int u , v;
        cin >> u >> v;
        int w = 10 * abs(u - v);
        adjt[u].push_back({v , w});
        adjt[v].push_back({u , w});
    }
    for (int u = 1 ; u <= k ; u++){
        for (int v = u + 1 ; v <= k ; v++){

            bool exist = false;
            for (auto smth : adjt[u]){
                int check = smth.first;
                if (check == v){
                    exist = true;
                    break;
                }
            }

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

        }
    }
    int result = max(re(k , k , adjc) , re(k , k , adjt));

    if (result == INT_MAX ){
        cout << -1;
    } else {
        cout << result;
    }
    
    return 0;
}