Submission

Score: 100

User: tha_smith

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

Language: cpp

Time: 0.009 second

Submitted On: 2026-03-07 22:52:57

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
	ios_base::sync_with_stdio(0),cin.tie(0);
	int N,M;
	cin >> N >> M;
	vector<vector<char>> edges(N+1,vector<char>(N+1,0));
	while(M--) {
		int a,b;
		cin >> a >> b;
		edges[a][b]=edges[b][a]=1;
	}
	bool useedge = edges[1][N];
	vector<ll> dist(N+1,1e18);
	vector<char> vis(N+1,0);
	priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
	dist[1]=0;
	pq.push({0,1});
	
	while(!pq.empty()) {
		auto [w,u] = pq.top();
		pq.pop();
		if(vis[u])
			continue;
		vis[u]=1;
		if(u==N)
			break;
		for(int v=1; v<=N; v++) {
			if(u==v)
				continue;
			bool isedge = useedge ? (!edges[u][v]):edges[u][v];
			if(!isedge)
				continue;
			ll ww = (ll)10*(abs(u-v));
			if(dist[v]>w+ww) {
				dist[v]=w+ww;
				pq.push({dist[v],v});
			}
		}
	}
	if(dist[N]>=1e18) {
		cout << -1;
	}
	else {
		cout << dist[N];
	}
}