Submission

[PPPPPPPPPPPPPPPPPPPP]

Score: 100

User: njoop

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

Language: cpp

Time: 0.018 second

Submitted On: 2025-03-09 23:56:02

#include <bits/stdc++.h>
#define int long long
#define pi pair<int, int>
using namespace std;

vector<pair<int, int>> gt[410], gc[410];
int n, m, u, v, cn, cd, nn, nd, edge[410][410], disc[410], dist[410];
priority_queue<pi, vector<pi>, greater<pi>> pq;

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    for(int i=1; i<=m; i++) {
        cin >> u >> v;
        edge[u][v] = 1;
        edge[v][u] = 1;
    }
    for(int i=1; i<=n; i++) {
        disc[i] = 1e18;
        dist[i] = 1e18;
        for(int j=1; j<=n; j++) {
            if(edge[i][j] == 1) gt[i].push_back({j, abs(i-j)*10});
            else gc[i].push_back({j, abs(i-j)*10});
        }
    }
    pq.push({0, 1});
    dist[1] = 0;
    while(pq.size()) {
        cd = pq.top().first;
        cn = pq.top().second;
        pq.pop();
        if(cd > dist[cn]) continue;
        for(auto i: gt[cn]) {
            nd = cd+i.second;
            nn = i.first;
            if(nd < dist[nn]) {
                dist[nn] = nd;
                pq.push({nd, nn});
            }
        }
    }
    pq.push({0, 1});
    disc[1] = 0;
    while(pq.size()) {
        cd = pq.top().first;
        cn = pq.top().second;
        pq.pop();
        if(cd > disc[cn]) continue;
        for(auto i: gc[cn]) {
            nd = cd+i.second;
            nn = i.first;
            if(nd < disc[nn]) {
                disc[nn] = nd;
                pq.push({nd, nn});
            }
        }
    }
    if(max(disc[n], dist[n]) == 1e18) cout << -1;
    else cout << max(disc[n], dist[n]);
    return 0;
}