Submission

[PPPPPPPPPPPPPPPPPPPP]

Score: 100

User: qwerty

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

Language: cpp

Time: 0.021 second

Submitted On: 2025-03-16 19:25:14

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

int dijkstra(vector<vector<pair<int, int>>> &path, int n) {
    // m+1
    vector<int> dis(n+1, INT_MAX);
    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 u = pq.top().second;
        pq.pop();

        for (auto i : path[u]) {
            int v = i.first;
            int w = i.second;
            if (dis[v]>dis[u]+w) {
                dis[v] = dis[u]+w;
                pq.push({dis[v], v});
            }
        }
    }

    return dis[n];
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> t_path(n+1);
    vector<vector<pair<int, int>>> c_path(n*4-n-1);
    int u, v;
    bool train = false;
    vector<vector<int>> keep(n+1, vector<int>(n+1, 0));
    for (int i = 0 ; i < m ; i++) {
        cin >> u >> v;
        t_path[u].push_back({v, 10*abs(v-u)});
        t_path[v].push_back({u, 10*abs(u-v)});
        if ((u==1 && v==n) || (u==n && v==1)) train = true;
        keep[u][v] = 1;
        keep[v][u] = 1;
    }
    int ans;
    if (train) {
        // cout << "-";
        vector<vector<pair<int, int>>> c_path(m+1);
        for (int i = 1 ; i <= n ; i++) {
            for (int j = 1 ; j <= n ; j++) {
                if (keep[i][j] == 0) {
                    c_path[i].push_back({j, 10*abs(j-i)});
                    c_path[j].push_back({i, 10*abs(i-j)});
                }
            }
        }
        ans = dijkstra(c_path, n);
    } else {
        // cout << "*";
        ans = dijkstra(t_path, n);
    }
    if (ans == INT_MAX) cout << -1;
    else cout << ans;
}