Submission

Score: 0

User: tha_smith

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

Language: cpp

Time: 0.003 second

Submitted On: 2026-03-03 23:15:22

#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;
	if (!(cin >> N >> M)) return 0;
	vector<vector<char>> edge(N+1,vector<char>(N+1,0));
	for(int i=0; i<M; ++i) {
		int a,b;
		cin >> a >> b;
		edge[a][b] = edge[b][a] = 1;
	}
	
	bool useedge = edge[1][N];
	ll dist[N+1];
	char vis[N+1];
	memset(dist,0x3f,sizeof(dist));
	memset(vis,0,sizeof(vis));
	priority_queue<pair<ll,int>> pq;
	dist[1] = 0;
	pq.push({0,1});
	//cout << dist[1] << '\n';
	while(!pq.empty()) {
		auto[u,v] = pq.top();
		pq.pop();
		if(vis[v])
			continue;
		vis[v] = 1;
		if(v==N)
			break;
			
		for(int vv=1; vv<=N; ++vv) {
			if(vv==v)
				continue;
			bool isedge = useedge ? (!edge[v][vv]):(edge[v][vv]);
			if(!isedge)
				continue;
			ll w = (ll)(10*abs(vv-v));
			//cout << w << ' ' << vv << ' ' << v << ' ' << u << ' ' << w << ' ' << u+w << ' ' << dist[vv] << '\n';
			if(dist[vv] > u+w) {
				dist[vv]=u+w;
				pq.push({dist[vv],vv});
				//cout << dist[vv] << ' ' << vv << '\n';
			}
		}
	}
	//cout << dist[N] << '\n';
	if(dist[N]>=1e18) {
		cout << -1;
	}
	else {
		cout << dist[N];
	}
}