Submission

Score: 100

User: klalnwza007

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

Language: cpp

Time: 0.008 second

Submitted On: 2025-10-10 09:38:29

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    if (!(cin >> N >> M)) return 0;

    // rail[u][v] = ???ҧ??????? (undirected)
    vector<vector<char>> rail(N+1, vector<char>(N+1, 0));
    for (int i = 0; i < M; ++i) {
        int U, V; cin >> U >> V;
        rail[U][V] = rail[V][U] = 1;
    }

    // ??????ҧ 1-N => ?? "???" (???????????ͧ rail)
    // ?????????ҧ 1-N => ?? "?ҧ"
    bool useRoad = rail[1][N];  // true -> ???ҿ???, false -> ???ҿ?ҧ

    const long long INF = (1LL<<60);
    vector<long long> dist(N+1, INF);
    vector<char> vis(N+1, 0);
    dist[1] = 0;

    // Dijkstra ????ҿ??????ҧẺ on-the-fly
    // ????? u-v ?????????:
    //   useRoad == true  => ??????ҧ (rail[u][v] == 0)
    //   useRoad == false => ???ҧ   (rail[u][v] == 1)
    priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> pq;
    pq.push({0,1});

    while (!pq.empty()) {
        auto [d,u] = pq.top(); pq.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        if (u == N) break; // ??????????ش?ͧ N ????

        for (int v = 1; v <= N; ++v) {
            if (v == u) continue;
            bool edgeExists = useRoad ? (!rail[u][v]) : (rail[u][v]);
            if (!edgeExists) continue;

            long long w = 10LL * llabs(v - u);
            if (dist[v] > d + w) {
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    }

    if (dist[N] >= INF/2) cout << -1 << '\n';
    else cout << dist[N] << '\n';

    return 0;
}