Submission

Score: 100

User: navysrimuang

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

Language: cpp

Time: 0.037 second

Submitted On: 2026-03-18 13:59:02

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e9;
int n,m;
vector<vector<pair<ll,int>>> train,road;

vector<ll> dijkstra(vector<vector<pair<ll,int>>> adj){
		vector<ll> dist(n+1,INF);
		dist[1] = 0;
		priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
		pq.push({0,1});
		while(pq.size()){
			auto [dis,node] = pq.top();
			pq.pop();
			if(dis > dist[node]) continue;

			for(auto [w,child] : adj[node]){
				if(dis + w < dist[child]){
					dist[child] = dis + w;
					pq.push({dist[child],child});
				}
			}

		}
		return dist;
}
int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	train.resize(n+1);
	road.resize(n+1);
	for(int i = 1;i<=n;i++){
			for(int j = 1;j<=n;j++){
				if(i == j) continue;
				road[i].push_back({10*abs(j-i),j});
			}
	}
	
	for(int i = 0;i<m;i++){
		int a,b;
		cin >> a >> b;
		ll c = 10*abs(a-b);
		train[a].push_back({c,b});
		train[b].push_back({c,a});
		road[a].erase(remove(road[a].begin(),road[a].end(),make_pair(c,b)),road[a].end());
		road[b].erase(remove(road[b].begin(),road[b].end(),make_pair(c,a)),road[b].end());
		
		
	}
	
	vector<ll> dt(n+1),dr(n+1);
	dt = dijkstra(train);
	dr = dijkstra(road);
	
	if(dt[n] == INF || dr[n] == INF) cout << -1 << "\n";
	else cout << max(dt[n],dr[n]) << "\n";
	return 0;
}