Submission

Score: 100

User: KantaponZ

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

Language: cpp

Time: 0.013 second

Submitted On: 2025-07-26 00:04:50

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

#define ll long long

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

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] = 1e18;
    if (con[1][N]) {
        for (int i = 1; i <= N; i++) {
            for (int j = i + 1; j <= N; j++) {
                if (con[i][j] || con[j][i]) 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] || con[j][i])) continue;
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
        }
    }
    pq.emplace(0, 1);
    dist[1] = 0;
    while (!pq.empty()) {
        
        auto [w, u] = pq.top();
        //cout << dist[u];
        pq.pop();
        w *= -1;
        for (auto v : adj[u]) {
            if (dist[v] <= w + 10 * abs(v - u)) continue;
            dist[v] = w + 10 * abs(v - u);
            pq.emplace(-(w + 10 * abs(v - u)), v);
        }
    }
    if (dist[N] == 1e18) {
        cout << -1;
    } else {
        cout << dist[N];
    }
}

/*

400 1
1 400

*/