Submission

Score: 0

User: KantaponZ

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

Language: cpp

Time: 0.650 second

Submitted On: 2025-07-25 22:53:41

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

const int maxN = 405;
int N, M;
bool con[405][405];
vector<vector<int>> adj(401);
priority_queue<pair<int,int>> pq;
int dist[401];

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> N >> M;
    while (M--) {
        int u, v;
        cin >> u >> v;
        con[u][v] = con[v][u] = 1;
    }
    for (int i = 1; i <= N; i++) dist[i] = 1e9;
    if (con[1][N]) {
        for (int i = 1; i < N; i++) {
            for (int j = i + 1; j <= N; j++) {
                if (con[i][j]) continue;
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
        }
    } else {
        for (int i = 1; i < N; i++) {
            for (int j = i + 1; j <= N; j++) {
                if (!con[i][j]) continue;
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
        }
    }
    pq.emplace(0, 1);
    while (!pq.empty()) {
        auto [w, u] = pq.top();
        pq.pop();
        w *= -1;
        if (dist[u] < w) continue;
        dist[u] = w;
        for (auto v : adj[u]) {
            if (dist[v] < w + 10 * abs(v - u)) continue;
            pq.emplace(-(w + 10 * abs(v - u)), v);
        }
    }
    if (dist[N] == 1e9) {
        cout << -1;
    } else {
        cout << max(10 * (N - 1), dist[N]);
    }
}