Submission

[PPPPPPPPPPPPPPPPPPPP]

Score: 100

User: Nozomi_boundfortokyo

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

Language: cpp

Time: 0.010 second

Submitted On: 2025-03-20 11:03:25

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int g[401][401];
int n,m;	
ll disttrain[401];
ll distcar[401];
ll findtrainfirst()
{
	priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,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])
			{
				distcar[v]=distcar[u]+10*abs(v-u);
				pq.push({distcar[v],v});
			}
		}
	}	
	//check whether it reach
	if(distcar[n]==1e9 || disttrain[n]==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;
	}
    ll d1=findtrainfirst();
	cout<<d1;
}