Submission

[PPPPPPPPPPPPPPPPPPPP]

Score: 100

User: mydKN

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

Language: cpp

Time: 0.125 second

Submitted On: 2025-03-14 05:01:23

#include<bits/stdc++.h>

using namespace std;

using pii = pair<int, int>;

struct stc{
	int w, ut, uc;
	bool operator<(const stc a) const{
		return w > a.w;
	}
};

const int maxn = 410;
const int inf = 2e9;

int n, m;
pii adj[maxn][maxn];
vector<int> distt(maxn, inf), distc(maxn, inf);
//bool visitedt[maxn], visitedc[maxn];
priority_queue<stc> pq;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin >> n >> m;
	for(int i=0;i<m;++i){
		int u, v, w;
		cin >> u >> v;
		w = abs(u - v) * 10;
		adj[u][v].first = w;
		adj[u][v].second = 1;
		adj[v][u].first = w;
		adj[v][u].second = 1;
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=i;++j){
			if(!adj[i][j].second){
				int w = abs(i - j) * 10;
				adj[i][j].first = w;
				adj[j][i].first = w;
			}
		}
	}
	distt[1] = 0;
	distc[1] = 0;
	pq.push(stc{0, 1, 1});
	while(!pq.empty()){
		auto [w, ut, uc] = pq.top();
		pq.pop();
		//if(visitedt[ut] || visitedc[uc] || (ut == uc && ut != 1 && uc != 1)) continue;
		if(ut == uc && ut != 1 && uc != 1) continue;
		//visitedt[ut] = 1;
		//visitedc[uc] = 1;
		for(int i=1;i<=n;++i){
			if(!adj[ut][i].second || i == ut) continue;
			for(int j=1;j<=n;++j){
				if(adj[uc][j].second || j == uc) continue;
				if(i != j){
					int omx = max(distt[i], distc[j]);
					int nmx = max(distt[ut] + adj[ut][i].first, distc[uc] + adj[uc][j].first);
					if(omx > nmx){
						distt[i] = distt[ut] + adj[ut][i].first;
						distc[j] = distc[uc] + adj[uc][j].first;
						pq.push(stc{nmx, i, j});
						//cout << nmx << " " << i << " " << j << "\n";
					}
				}
			}
		}
		//cout << ut << " " << uc << "\n";
	}
	int res = max(distt[n], distc[n]);
	if(res == inf) cout << -1;
	else cout << res;
}