Submission

Score: 100

User: Shangbin

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

Language: cpp

Time: 0.009 second

Submitted On: 2026-03-19 22:36:55

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

#define pii pair<int, int>

const int maxn = 405, inf = 1e9;
int n, m, u, v, visited[maxn], parent[maxn], dist[maxn];
bool connect[maxn][maxn];
bool train_skip = 0;
vector<int> adj[maxn], adjcar[maxn];
priority_queue<pii, vector<pii>, greater<pii>> pq;

int main(){
    cin.tie(nullptr)->sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 0; i < m; i++){
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        connect[u][v] = 1;
        connect[v][u] = 1;
        if ((u == 1 && v == n) || (u == n && v == 1)) train_skip = 1;
    }
    if (train_skip){
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= n; j++){
                if (connect[i][j] || connect[j][i]) continue;
                adjcar[i].push_back(j);
            }
        }
    }
    for (int i = 0; i <= n; i++) dist[i] = inf;
    dist[1] = 0;
    pq.push({0, 1});
    while (!pq.empty()){
        auto [d, u] = pq.top(); pq.pop();
        if (visited[u]) continue;
        visited[u] = 1;
        if (train_skip){
            for (int v : adjcar[u]){
                int new_dist = dist[u] + (10 * abs(v - u));
                if (new_dist < dist[v]){
                    dist[v] = new_dist;
                    parent[v] = u;
                    pq.push({dist[v], v});
                }
            }
        }
        else {
            for (int v : adj[u]){
                int new_dist = dist[u] + (10 * abs(v - u));
                if (new_dist < dist[v]){
                    dist[v] = new_dist;
                    parent[v] = u;
                    pq.push({dist[v], v});
                }
            }
        }
    }
    if (!visited[n]) return cout << -1, 0;
    cout << dist[n] << '\n';
}