Submission

Score: 100

User: boomm

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

Language: cpp

Time: 0.027 second

Submitted On: 2026-03-12 20:40:33

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,m;
	cin >> n >> m;
	vector<vector<int> > vt(m,vector<int>(2));
	vector<vector<pair<int,int> > > v(n+1);
	vector<vector<pair<int,int> > > vv(n+1);
	vector<vector<bool> > rail(405,vector<bool>(405,false));
	vector<int> dist(n+1,1e9);
	vector<int> distt(n+1,1e9);
	dist[1]=0;
	distt[1]=0;
	for(int i=0;i<m;i++){
		cin >> vt[i][0] >> vt[i][1];
	}
	for(int i=0;i<m;i++){
		int a=vt[i][0];
		int b=vt[i][1];
		int c=10*abs(a-b);
		rail[a][b]=true; rail[b][a]=true;
		v[a].push_back({b,c});
		v[b].push_back({a,c});
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(rail[i][j]==false){
				int c=10*abs(i-j);
				vv[i].push_back({j,c});
				vv[j].push_back({i,c});
			}
		}
	}
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;
	pq.push({0,1});
	while(!pq.empty()){
		int u=pq.top().second;
		int d=pq.top().first;
		pq.pop();
		if(d>dist[u]) continue;
		for(int i=0;i<v[u].size();i++){
			int x=v[u][i].first;
			int w=v[u][i].second;
			if(dist[x] > dist[u]+w){
				dist[x]=dist[u]+w;
				pq.push({dist[x],x});
			}
		}
	}
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pqq;
	pqq.push({0,1});
	while(!pqq.empty()){
		int u=pqq.top().second;
		int d=pqq.top().first;
		pqq.pop();
		if(d>distt[u]) continue;
		for(int i=0;i<vv[u].size();i++){
			int x=vv[u][i].first;
			int w=vv[u][i].second;
			if(distt[x] > distt[u]+w){
				distt[x]=distt[u]+w;
				pqq.push({distt[x],x});
			}
		}
	}
	if(dist[n]==1e9 || distt[n]==1e9){
		cout << "-1";
	}
	else cout << max(dist[n],distt[n]);
	return 0;
}