Submission

Score: 100

User: dddrrrr

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

Language: cpp

Time: 0.018 second

Submitted On: 2026-03-11 10:47:56

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

int dijk(vector <vector <pair <int ,int>>> &adj ,int n){
	priority_queue <pair <int,int> ,vector <pair <int,int>> ,greater <pair <int,int>>> pq;
	vector <int> dist(n+1 ,LLONG_MAX);
	
	pq.push({0 ,1});
	dist[1] = 0;
	
	while(!pq.empty()){
		int d=pq.top().first ,u=pq.top().second;
		pq.pop();
		
		if(d > dist[u])continue;
		
		for(auto &nxt : adj[u]){
			int v=nxt.first ,w=nxt.second;
			if(d + w < dist[v]){
				dist[v] = d+w;
				pq.push({dist[v] ,v});
			}
		}
	}
	
	return dist[n];
}

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int n ,m;cin >> n >> m;
	vector <vector <pair <int ,int>>> train(n+1) ,car(n+1);
	while(m--){
		int u, v;
		cin >> u >> v;
		int w = abs(u - v)*10;
		train[u].emplace_back(v ,w);
		train[v].emplace_back(u, w);
	}
	
	for(int i=1 ;i<=n ;i++){
		unordered_set <int> s;
		for(auto j : train[i])s.insert(j.first);
		
		//cout << "i" << "\n";
		for(int j=1 ;j<=n ;j++){
			if(!s.count(j) && i != j){
				//cout << i << ' ' << j << '\n';
				int w = abs(i - j)*10;
				car[i].emplace_back(j ,w);
				car[j].emplace_back(i ,w);
			}
		}
		//cout << "next\n";
	}
	
	int a = dijk(train ,n);
	int b = dijk(car ,n);
	int mx = max(a ,b);
	if(mx == LLONG_MAX)cout << -1;
	else cout << mx;
	
	return 0;
}