Submission

[PPP-SSSSSSSSSSSSSSSS]

Score: 0

User: Nozomi_boundfortokyo

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

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-20 10:23:24

#include <bits/stdc++.h>
using namespace std;
int g[401][401];
int n,m;	
int disttrain[401];
int distcar[401];
int findtrainfirst()
{
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
	for(int i=1;i<=n;i++)
	{
		disttrain[i]=1e9;
		distcar[i]=1e9;
	}
	disttrain[1]=0;
	distcar[1]=0;
	pq.push({0,1});
	while(!pq.empty())
	{
		int u=pq.top().second;
		pq.pop();
		for(int v=1;v<=n;v++)
		{
			if(!g[u][v]) continue;
			if(disttrain[u]+10*abs(v-u)<disttrain[v])
			{
				disttrain[v]=disttrain[u]+10*abs(v-u);
				pq.push({disttrain[v],v});
			}
		}
	}
//	pq.push({0,1});
	while(!pq.empty())
	{
		int u=pq.top().second;
		pq.pop();
		for(int v=1;v<=n;v++)
		{
			if(g[u][v]) continue;
			else if(distcar[u]+10*abs(v-u)<distcar[v])
			{
				if(distcar[u]+10*abs(v-u)==disttrain[v] && v!=1 && v!=n) continue;
				distcar[v]=distcar[u]+10*abs(v-u);
				pq.push({distcar[v],v});
			}
		}
	}	
	//check whether there is 1e9 in distcar
	for(int i=2;i<=n-1;i++)
	{
		if(distcar[i]==1e9)
		  return -1;
	}
	return max(disttrain[n],distcar[n]);
}
int findcarfirst()
{
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
	int disttrain[401];
	int distcar[401];
	for(int i=1;i<=n;i++)
	{
		disttrain[i]=1e9;
		distcar[i]=1e9;
	}
	disttrain[1]=0;
	distcar[1]=0;
	pq.push({0,1});
	while(!pq.empty())
	{
		int u=pq.top().second;
		pq.pop();
		for(int v=1;v<=n;v++)
		{
			if(g[u][v]) continue;
			if(distcar[u]+10*abs(v-u)<distcar[v])
			{
				distcar[v]=distcar[u]+10*abs(v-u);
				pq.push({distcar[v],v});
			}
		}
	}
	pq.push({0,1});
	while(!pq.empty())
	{
		int u=pq.top().second;
		pq.pop();
		for(int v=1;v<=n;v++)
		{
			if(g[u][v]) continue;
			if(disttrain[u]+10*abs(v-u)<disttrain[v])
			{
				if(disttrain[u]+10*abs(v-u)==disttrain[v] && v!=1 && v!=n) continue;
				disttrain[v]=disttrain[u]+10*abs(v-u);
				pq.push({disttrain[v],v});
			}
		}
	}	
	//check whether there is 1e9 in distcar
	for(int i=2;i<=n-1;i++)
	{
		if(disttrain[i]==1e9)
		  return -1;
	}
	return max(disttrain[n],distcar[n]);
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		int u,v;
		cin>>u>>v;
		g[u][v]=1; //1 is train 0 is car
		g[v][u]=1;
	}
	int d1=findtrainfirst();
	int d2=findcarfirst();
	if(d1==-1 && d2==-1)
	{
		cout<<-1;
	}
	else if(d1==-1)
	{
		cout<<d2;
	}
	else if(d2==-1)
	{
		cout<<d1;
	}
	else if(d1<=d2)
	{
		cout<<d1;
	}
	else if(d1>d2)
	{
		cout<<d2;
	}
}