Submission

Score: 100

User: meme_boi2

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

Language: cpp

Time: 0.011 second

Submitted On: 2026-03-18 19:40:18

#include <bits/stdc++.h>
using namespace std;
bool chk[401][401];
vector<vector<pair<int,int>>> path(401),graph(401);
#define pii pair<int,int>
int32_t main(){
    cin.tie(nullptr)->sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    while(m--){
        int u, v;
        cin >> u >> v;
        chk[u][v] = 1;
        chk[v][u] = 1;
        path[u].push_back({v,abs(u-v)*10});
        path[v].push_back({u,abs(u-v)*10});
    }
    for(int i = 1; i<= n; i++){
        for(int j = i+ 1; j <= n; j++){
            if(i != j && !chk[i][j]){
                graph[i].push_back({j,abs(i-j)*10});
                graph[j].push_back({i,abs(i-j)*10});
            }
        }
    }
    priority_queue<pii,vector<pii>,greater<pii>> pq;
    vector<int> dist(401,1e9);
    if(!chk[1][n]){
        dist[1] = 0;
        pq.push({0,1});
        while(!pq.empty()){
            auto [w,u] = pq.top();
            pq.pop();
            if(dist[u] < w) continue;
            for(auto [v,x] : path[u]){
                if(dist[u] + x < dist[v]){
                    pq.push({dist[v] = dist[u] + x,v});
                }
            }
        }
    }else{
        dist[1] = 0;
        pq.push({0,1});
        while(!pq.empty()){
            auto [w,u] = pq.top();
          //  cout << u << ' ' << w << " kungaroo\n";
            pq.pop();
            if(dist[u] < w) continue;
            for(auto [v,x] : graph[u]){
                if(dist[u] + x < dist[v]){
                    pq.push({dist[v] = dist[u] + x,v});
                }
            }
        }
    }
   // cout << "Distance : " << dist[n] << '\n';
    int ans = max(dist[n],10*n - 10);
    if(ans > 1e9 - 7){
        cout << -1;
    }else{
        cout << ans;
    }
}