Submission

Score: 0

User: KantaponZ

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

Language: cpp

Time: 0.587 second

Submitted On: 2025-07-25 22:59:23

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

#define ll long long
const int maxN = 405;
int N, M;
bool con[1000][1000];
vector<vector<ll>> adj(1000);
priority_queue<pair<ll,ll>> pq;
ll dist[1000];

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]) 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] == 1e18) {
        cout << -1;
    } else {
        cout << max(10 * 1LL * (N - 1), dist[N]);
    }
}