Submission

Score: 100

User: VggT

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

Language: cpp

Time: 0.042 second

Submitted On: 2026-03-12 16:14:16

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

void path(vector<vector<pair<int,int>>> &vehiclesPath, vector<int> &dist)
{
	priority_queue<pair<int,int>, vector<pair<int,int>> , greater<pair<int,int>> > pq;
	pq.push({0,0});
	while(!pq.empty())
	{
		int node = pq.top().second;
		int distant = pq.top().first;
		pq.pop();
		for(auto neighbors : vehiclesPath[node])
		{
			if(dist[neighbors.first] > distant+neighbors.second)
			{
				dist[neighbors.first] = distant+neighbors.second;
				pq.push({dist[neighbors.first],neighbors.first});
			}
		}
	}
}

int main()
{
	int n, m; cin >> n >> m;
	vector<vector<pair<int,int>>> trainspath(n);
	vector<vector<pair<int,int>>> roadspath(n);
	vector<int> trainsDist(n,INT_MAX);
	vector<int> roadsDist(n,INT_MAX);
	vector<unordered_set<int>> contains(n);
	for(int i = 0; i < m; i+=1)
	{
		int u,v; cin >> u >> v;
		u-=1; v-=1;
		trainspath[u].push_back({v,10*abs(v-u)});
		trainspath[v].push_back({u,10*abs(u-v)});
		contains[u].insert(v);
		contains[v].insert(u);
	}
	
	
	for(int i = 0; i < n; i+=1)
	{
		for(int j = 0; j < n; j+=1)
		{
			if(contains[i].count(j)) continue;
			roadspath[i].push_back({j,10*abs(j-i)});
			roadspath[i].push_back({i,10*abs(i-j)});
		}
	}
	
	
	path(trainspath,trainsDist);
	path(roadspath,roadsDist);
	
	
	
	
	
	if(trainsDist[n-1] == INT_MAX || roadsDist[n-1] == INT_MAX) cout << -1;
	else cout << max(trainsDist[n-1],roadsDist[n-1]);
	
	
	
	return 0;
}