Submission

[PPPPPPPPPPPPPPPPP-SS]

Score: 0

User: ftm

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

Language: cpp

Time: 0.014 second

Submitted On: 2025-03-14 11:30:05

#include<bits/stdc++.h>
using namespace std;
#define f(i,a,b,c) for(int i=a;i<=b;i+=c)
#define r(i,a,b,c) for(int i=a;i>=b;i-=c)
#define fi first
#define se second
#define pb push_back
using ll=long long int;
using pii=array<int,2>;
const int N=500;
const int inf=1e9;
int adj[N][N];
vector<pii> g[2][N];
priority_queue<pii,vector<pii>,greater<pii>> q;
vector<vector<int>> dis(4,vector<int>(N,inf));
bool vis[4][N];


int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	int n,m;cin>>n>>m;
	f(i,1,m,1) {
		int u,v;
		cin>>u>>v;
		adj[u][v]=1;
		adj[v][u]=1;
	}
	f(i,1,n,1){
		f(j,i+1,n,1){
			if(adj[i][j]){
				g[0][i].pb({j,10*(j-i)});
				g[0][j].pb({i,10*(j-i)});
			}
			else{
				g[1][i].pb({j,10*(j-i)});
				g[1][j].pb({i,10*(j-i)});
			}
		}
	}
	dis[0][1]=0;
	q.push({0,1});
	while(!q.empty()){
		int u=q.top()[1];
		int d=q.top()[0];
		//cout<<u<<" "<<d<<"\n";
		q.pop();
		if(u==n){
			break;
		}
		if(vis[0][u]) continue;
		vis[0][u]=1;
		for(auto e:g[0][u]){
			int v=e[0];
			int w=e[1];
			//cout<<v<<":"<<w<<" :: "<<dis[0][v]<<"\n";
			if(!vis[0][v] && dis[0][v]>dis[0][u]+w){
				dis[0][v]=dis[0][u]+w;
				q.push({dis[0][v],v});
			}
		}
	}
	if(dis[0][n]==inf){
		cout<<-1;
		return 0;
	}
	//cout<<dis[0][n]<<"\n\n";
	while(!q.empty()) q.pop();
	
	dis[1][1]=0;
	q.push({0,1});
	while(!q.empty()){
		int u=q.top()[1];
		int d=q.top()[0];
		q.pop();
		if(u==n){
			break;
		}
		if(vis[1][u]) continue;
		vis[1][u]=1;
		for(auto e:g[1][u]){
			int v=e[0];
			int w=e[1];
			if(v!=n && dis[1][u]+w==dis[0][v]) continue;
			if(!vis[1][v] && dis[1][v]>dis[1][u]+w){
				dis[1][v]=dis[1][u]+w;
				q.push({dis[1][v],v});
			}
		}
	}
	if(dis[1][n]==inf){
		cout<<-1;
		return 0;	
	}
	
	
	int ans=max(dis[1][n],dis[0][n]);
	
	dis[3][1]=0;
	q.push({0,1});
	while(!q.empty()){
		int u=q.top()[1];
		int d=q.top()[0];
		//cout<<u<<" "<<d<<"\n";
		q.pop();
		if(u==n){
			break;
		}
		if(vis[3][u]) continue;
		vis[3][u]=1;
		for(auto e:g[1][u]){
			int v=e[0];
			int w=e[1];
			if(!vis[3][v] && dis[3][v]>dis[3][u]+w){
				dis[3][v]=dis[3][u]+w;
				q.push({dis[3][v],v});
			}
		}
	}
	
	while(!q.empty()) q.pop();
	
	dis[2][1]=0;
	q.push({0,1});
	while(!q.empty()){
		int u=q.top()[1];
		int d=q.top()[0];
		q.pop();
		if(u==n){
			break;
		}
		if(vis[2][u]) continue;
		vis[2][u]=1;
		for(auto e:g[0][u]){
			int v=e[0];
			int w=e[1];
			if(v!=n && dis[2][u]+w==dis[3][v]) continue;
			if(!vis[2][v] && dis[2][v]>dis[2][u]+w){
				dis[2][v]=dis[2][u]+w;
				q.push({dis[2][v],v});
			}
		}
	}
	if(dis[2][n]==-1 || dis[3][n]==-1) cout<<ans;
	else{
		cout<<min(ans,max(dis[2][n],dis[3][n]));
	}
	
}