Submission

Score: 0

User: tha_smith

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

Language: cpp

Time: 0.002 second

Submitted On: 2026-03-04 22:30:54

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

int main() {
    ios_base::sync_with_stdio(0),cin.tie(0);
    int N,M;
    cin >> N >> M;
    vector<vector<char>> edge(N+1,vector<char> (N+1,0));
    for(int i=0; i<M; i++) {
        int a,b;
        cin >> a >> b;
        edge[a][b] = edge[b][a] = 1;
    }
    bool useedge = edge[1][N];
    vector<ll> dist(N+1,0x3f);
    vector<char> vis(N+1,0);
    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
    dist[1]=0;
    pq.push({0,1});
    
    while(!pq.empty()) {
        auto[w,u] = pq.top();
        pq.pop();
        if(vis[u])
            continue;
        vis[u]=1;
        if(u==N)
            break;
        for(int v=1; v<=N; v++) {
            if(u==v)
                continue;
            bool isedge = useedge ? (!edge[u][v]):(edge[u][v]); //if there's path from 1->N ignore real paths and accumulate fake paths instead, else use real paths
            if(!isedge)
                continue;
            ll ww = (ll)(10*(abs(v-u)));
            if(dist[v]>w+ww) {
                dist[v] = w+ww;
                pq.push({dist[v],v});
            }
        }
    }
    if(dist[N]>=1e18) {
        cout << -1;
    }
    else {
        cout << dist[N];
    }
}