Submission

Score: 100

User: nemuchannnUwU

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

Language: cpp

Time: 0.015 second

Submitted On: 2026-03-11 13:52:54

#include<bits/stdc++.h>
#define int long long
using namespace std;
int solve(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);
	dist[1]=0;
	pq.push({0,1});
	while(!pq.empty()){
		int d=pq.top().first;
		int u=pq.top().second;
		pq.pop();
		if (d>dist[u]) continue;
		for (auto &p : adj[u]){
			int w=p.second;
			int v=p.first;
			if (dist[v]>d+w){
				dist[v]=d+w;
				pq.push({dist[v],v});
			}
		}
	}
	return dist[n];
}
main(){
	cin.tie(nullptr)->sync_with_stdio(0);
	bool has_rail[405][405]={false};
	int n,m; cin >> n >> m;
	vector<vector<pair<int,int>>> rail(n+1),road(n+1);
	for (int i=0;i<m;i++){
		int v,u; cin >> v >> u;
		has_rail[v][u]=has_rail[u][v]=true;
	}
	for (int i=1;i<=n;i++){
		for (int j=1+1;j<=n;j++){
			int w=10*abs(i-j);
			if (has_rail[i][j]){
				rail[i].push_back({j,w});
				rail[j].push_back({i,w});
			}else{
				road[i].push_back({j,w});
				road[j].push_back({i,w});
			}
		}
	}
	
	int ro=solve(road,n);
	int ra=solve(rail,n);
	if (ro==LLONG_MAX||ra==LLONG_MAX) cout << -1;
	else cout << max(ro,ra);
}