Submission

Score: 100

User: lufychop

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

Language: cpp

Time: 0.038 second

Submitted On: 2025-03-14 14:20:55

#include <bits/stdc++.h>

using namespace std;

int main(void)
{
	priority_queue<pair<long long,long long>,vector<pair<long long,long long>>,greater<pair<long long,long long>>> pq;
	vector<vector<bool>> adjmatrix(401,vector<bool>(401,false));
	vector<vector<long long>> adj(401);
	vector<long long> dis(401,1e18);
	long long n,m,t1,t2;
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		cin>>t1>>t2;
		adjmatrix[t1][t2]=true;
		adjmatrix[t2][t1]=true;
	}
	if(adjmatrix[1][n])
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=i+1;j<=n;j++)
			{
				if(adjmatrix[i][j])
				{
					continue;
				}
				adj[i].push_back(j);
				adj[j].push_back(i);
			}
		}
	}
	else
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=i+1;j<=n;j++)
			{
				if(adjmatrix[i][j])
				{
					adj[i].push_back(j);
					adj[j].push_back(i);
				}
			}
		}
	}
	dis[1]=0;
	pq.push({0,1});
	while(!pq.empty())
	{
		t1=pq.top().first;
		t2=pq.top().second;
		pq.pop();
		if(dis[t2]<t1)
		{
			continue;
		}
		for(int i=0;i<adj[t2].size();i++)
		{
			if(dis[adj[t2][i]]>t1+abs(adj[t2][i]-t2))
			{
				dis[adj[t2][i]]=t1+abs(adj[t2][i]-t2);
				pq.push({dis[adj[t2][i]],adj[t2][i]});
			}
		}
	}
	if(dis[n]==1e18)
	{
		cout<<-1;
		return 0;
	}
	cout<<10*dis[n];
	return 0;
}	
/*
5 3
1 3
3 4
4 5
*/