Submission

Score: 100

User: Nay-O

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

Language: cpp

Time: 0.009 second

Submitted On: 2026-03-16 22:47:39

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;

const int N = 405;

bool vis[N], p[N][N];

priority_queue<pii,vector<pii>,greater<pii>> q;



int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	
	int n,m; cin>>n>>m;
	
	for(int i = 0; i < m; i++){
		int a,b; cin>>a>>b;
		p[a][b]=true;
		p[b][a]=true;
	}
	q.push({0,1});
	if(p[1][n]){
		while(!q.empty()){
			int a = q.top().first, b = q.top().second;
			q.pop();
			if(vis[b]) continue;
			vis[b]=true;
			if(b == n){
				cout << a*10;
				return 0;
			}
			
			for(int i = 1; i <= n; i++){
				if(vis[i]||p[b][i]) continue;
				q.push({a+abs(i-b),i});
			}
		}
		cout << -1;
		return 0;
	}
	while(!q.empty()){
		int a = q.top().first, b = q.top().second;
		q.pop();
		if(vis[b]) continue;
		vis[b]=true;
		if(b == n){
			cout << a*10;
			return 0;
		}
		for(int i = 1; i <= n; i++){
			if(vis[i]||!p[b][i]) continue;
			q.push({a+abs(i-b),i});
		}
	}
	cout << -1;
	return 0;
}