Submission

Score: 100

User: poni

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

Language: cpp

Time: 0.073 second

Submitted On: 2026-10-11 22:02:44

#include <bits/stdc++.h>

using namespace std;
#define int long long 
#define INF 2e15
#define vi vector<int>
#define pii pair<int, int>
#define piii tuple<int, int, int>

signed main() {
    cin.tie(0)->sync_with_stdio(0);

    int n, m;
    cin >> n >> m;

    vector<vector<pii>> v1(n+1);
    vector<vector<pii>> v2(n+1);
    set<pii> used;
    while (m--) {
        int a, b;
        cin >> a >> b;
        v1[a].emplace_back(b, 10*abs(b-a));
        v1[b].emplace_back(a, 10*abs(b-a));
        used.emplace(a, b);
        used.emplace(b, a);
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) continue;
            if (used.count({i, j}) == 0) {
                v2[i].emplace_back(j, 10*abs(j-i));
            }
        }
    }

    auto djk = [&](const vector<vector<pii>> &v) {
        vi dist(n+1, INF);
        priority_queue<pii, vector<pii>, greater<pii>> pq;

        dist[1] = 0;
        pq.emplace(0, 1);

        while (!pq.empty()) {
            auto [cd, ci] = pq.top();
            pq.pop();

            if (cd > dist[ci]) continue;
            for (auto [ni, nd] : v[ci]) {
                if (cd + nd < dist[ni]) {
                    dist[ni] = cd + nd;
                    pq.emplace(dist[ni], ni);
                }
            }
        }
        return dist[n];
    };

    int ans = max(djk(v1), djk(v2));
    if (ans < INF) cout << ans;
    else cout << -1;
}