Submission

Score: 100

User: nik121416

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

Language: cpp

Time: 0.023 second

Submitted On: 2026-03-19 09:56:24

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

const int inf = 1e9+7;

int main(){
    int node,path;
    cin >> node >> path;
    vector<vector<bool>> adj_martrix(node,vector<bool>(node,false));
    vector<vector<pair<int,int>>> train(node);
    vector<vector<pair<int,int>>> road(node);
    for(int i = 0 ;i < path;i++){
        int u,v;
        cin >> u >> v;
        u-=1;
        v-=1;
        int w = 10*abs(u-v);
        train[u].push_back({w,v});
        train[v].push_back({w,u});
        adj_martrix[u][v] = true;
        adj_martrix[v][u] = true;
    }
    for(int i = 0 ; i < node;i++){
        for(int j= 0; j < node;j++){
            if(i != j && !adj_martrix[i][j]){
                int w = 10*abs(i-j);
                road[i].push_back({w,j});
                road[j].push_back({w,i});
            }
        }
    }
    vector<int> dis_road(node,inf);
    vector<int> dis_train(node,inf);
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    pq.push({0,0});
    dis_train[0] = 0;
    while(!pq.empty()){
        int w = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        for(auto [ww,v] : train[u]){
            if(ww + w < dis_train[v]){
                dis_train[v] = ww+w;
                pq.push({ww+w,v});
            }
        }
    }
    pq.push({0,0});
    dis_road[0] = 0;
    while(!pq.empty()){
        int w = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        for(auto [ww,v] : road[u]){
            if(ww + w < dis_road[v]){
                dis_road[v] = ww+w;
                pq.push({ww+w,v});
            }
        }
    }
    int mx = max(dis_road[node-1],dis_train[node-1]);
    if(mx == inf){
        cout << -1;
    }
    else{
        cout << mx;
    }
}