Submission

Score: 100

User: qweqwe

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

Language: cpp

Time: 0.036 second

Submitted On: 2025-10-21 20:06:06

#include <bits/stdc++.h>
#define speed cin.tie(0)->sync_with_stdio(0)
#define ll long long
#define pii pair<int,int>
#define INF 1e9
using namespace std;

// 1<=n<=400
vector<unordered_set<int>> used(401);
vector<vector<int>> rail(401),road(401);

int main(){
	speed;
	int n,m;cin >> n >> m;
	
	// rail building
	for (int i=0;i<m;i++){
		int u,v;cin >> u >> v;
		
		// for rails
		rail[u].push_back(v);
		rail[v].push_back(u);
		
		// for roads
		used[u].insert(v);
		used[v].insert(u);
	}
	
	// road building
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			if (!used[i].count(j)){
				road[i].push_back(j);
			}
		}
	}
	
	// 1st stp (rails)
	vector<int> disrail(n+1,INF),disroad(n+1,INF);
	disrail[1]=0;disroad[1]=0;
	priority_queue<pii> stp;stp.push({0,1});
	while (!stp.empty()){
		pii temp=stp.top();stp.pop();
		//cout << temp.first << " " << temp.second << "\n";
		for (int i:rail[temp.second]){
			int sum=temp.first+10*abs(i-temp.second);
			if (disrail[i]>sum){
				stp.push({sum,i});
				disrail[i]=sum;
			}
		}
	}//cout << disrail[n];
	
	//2nd stp (roads)
	stp.push({0,1});
	while (!stp.empty()){
		pii temp=stp.top();stp.pop();
		//cout << temp.first << " " << temp.second << "\n";
		for (int i:road[temp.second]){
			int sum=temp.first+10*abs(i-temp.second);
			if (disroad[i]>sum){
				stp.push({sum,i});
				disroad[i]=sum;
			}
		}
	}
	// unreachable
	if (disrail[n]==INF || disroad[n]==INF) cout << -1;
	// reachable
	else cout << max(disrail[n],disroad[n]);
	return 0;
}