Submission

Score: 100

User: mightbeputter

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

Language: cpp

Time: 0.013 second

Submitted On: 2026-03-27 13:29:13

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

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int n,m;
    cin >> n >> m;
    vector<vector<int>> edg(n+1);
    bool skip = false;
    for(int i=1;i<=m;i++){
        int u,v;
        cin >> u >> v;
        edg[u].push_back(v);
        edg[v].push_back(u);
        if((u == 1 && v == n) || (u == n && v == 1)) skip = 1;
    }
    if(skip){
        vector<vector<int>> temp(n+1);
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                if(find(edg[i].begin(), edg[i].end(), j) == edg[i].end()){
                    temp[i].push_back(j);
                    temp[j].push_back(i);
                }
            }
        }
        edg = temp;
    }
    vector<int> dis(n+1, 1e9);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    dis[1] = 0;
    pq.push({0,1});
    while(!pq.empty()){
        int w = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        for(int& x : edg[u]){
            int val = w + 10*abs(x-u);
            if(dis[x] <= val) continue;
            dis[x] = val;
            pq.push({dis[x], x});
        }
    }
    cout << ((dis[n] < 1e9) ? dis[n] : -1);
    return 0;
}