Submission

Score: 0

User: Hxluk.ka

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

Language: cpp

Time: 0.003 second

Submitted On: 2026-03-08 22:05:20

#include <iostream>
#include <vector>
#include <queue>
#define vt vector
#define pli pair<ll, int>
#define ll long long
using namespace std;
const ll nx=403, inf=4e18;
int n, m, u, v, key[nx][nx];
vector<int> tadj[nx], cadj[nx];
ll tdist[nx], cdist[nx];
priority_queue<pli, vt<pli>, greater<pli>> pq;
int main() {
    cin.tie(0)->sync_with_stdio(0);
    
    cin>>n>>m;
    for (int i=0; i<n; i++) cin>>u>>v, key[u][v]=key[v][u]=1;
    for (int i=1; i<=n; i++) tdist[i]=inf;
    for (int i=1; i<=n; i++) cdist[i]=inf;
    for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) {if (key[i][j]) tadj[i].push_back(j); else cadj[i].push_back(j);}
    
    pq.push({0, 1});
    tdist[1]=0;
    while (!pq.empty()) {
        auto [d, c]=pq.top(); pq.pop();
        if (d>tdist[c]) continue;
        for (auto i:tadj[c]) {
            if (tdist[i]>(10ll * abs(i-c))+d) {
                tdist[i]=tdist[c]+(10ll * abs(i-c));
                pq.push({tdist[i], i});
            }
        }
    }

    pq.push({0, 1});
    cdist[1]=0;
    while (!pq.empty()) {
        auto [d, c]=pq.top(); pq.pop();
        if (d>cdist[c]) continue;
        for (auto i:cadj[c]) {
            if (cdist[i]>(10ll * abs(i-c))+d) {
                cdist[i]=cdist[c]+(10ll * abs(i-c));
                pq.push({cdist[i], i});
            }
        }
    }

    if (cdist[n]==inf || tdist[n]==inf) cout<<-1;
    else cout<<max(cdist[n], tdist[n]);
}