Submission

Score: 100

User: chawinkn

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

Language: cpp

Time: 0.023 second

Submitted On: 2025-03-17 18:04:21

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

#define ll long long
#define pii pair<ll,ll>

vector<pii> g[409], G[409];
vector<int> d(409, 1e9), D(409, 1e9);
priority_queue<pii,vector<pii>,greater<pii>> pq;
bool t[409][409];
int n, m;

void dijkstra(vector<pii> g[], vector<int>& dist) {
	pq.push({dist[1]=0, 1});
	while (!pq.empty()) {
		auto [d,u] = pq.top(); pq.pop();
		for (auto [v,w] : g[u]) {
			if (dist[u]+w < dist[v]) pq.push({dist[v]=dist[u]+w, v});
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> m;
	while (m--) {
		int u, v;
		cin >> u >> v;
		g[u].push_back({v, 10*abs(u-v)});
		g[v].push_back({u, 10*abs(u-v)});
		t[u][v] = t[v][u] = true;
	}
	for (int u = 1; u <= n; u++) {
		for (int v = 1; v <= n; v++) {
			if (t[u][v]) continue;
			G[u].push_back({v, 10*abs(u-v)});
			G[v].push_back({u, 10*abs(u-v)});
		}
	}
	dijkstra(g, d), dijkstra(G, D);
	if (d[n] == 1e9 || D[n] == 1e9) cout << -1;
	else cout << max(d[n], D[n]);
	return 0;
}