Submission

[PPPPPPPPPPPPPPPPPPPP]

Score: 100

User: njoop

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

Language: cpp

Time: 0.011 second

Submitted On: 2025-03-09 23:55:58

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

vector<pair<int, int>> g[410];
int n, m, u, v, cn, cd, nn, nd, edge[410][410], dis[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++) {
        dis[i] = 1e18;
        for(int j=1; j<=n; j++) {
            if(edge[i][j] != edge[1][n]) {
                g[i].push_back({j, abs(i-j)*10});
            }
        }
    }
    pq.push({0, 1});
    dis[1] = 0;
    while(pq.size()) {
        cd = pq.top().first;
        cn = pq.top().second;
        pq.pop();
        if(cd > dis[cn]) continue;
        for(auto i: g[cn]) {
            nd = cd+i.second;
            nn = i.first;
            if(nd < dis[nn]) {
                dis[nn] = nd;
                pq.push({nd, nn});
            }
        }
    }
    if(dis[n] == 1e18) cout << -1;
    else cout << dis[n];
    return 0;
}