Submission

[PPPPPPPPPPPPPPPPPPPP]

Score: 100

User: krittaphot

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

Language: cpp

Time: 0.034 second

Submitted On: 2025-03-16 13:54:25

#include <bits/stdc++.h>

using namespace std;


void dijkstra(int start,vector<vector<int>> &path,vector<int> &dist){
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
	
	dist[start] = 0;
	pq.push({0,start});
	
	while(!pq.empty())
	{
		int time = pq.top().first;
		int node = pq.top().second;
		pq.pop();
		
		if(time > dist[node]) continue;
		
		for(auto i : path[node]){
			int new_time = time+10*abs(i-node);
			if(new_time < dist[i]){
				pq.push({new_time,i});
				dist[i] = new_time;
			}
		}
	}
}


int main()
{
	int n,m;
	cin >> n >> m;
	vector<vector<bool>> is_rail(n+1, vector<bool>(n+1, false));
	vector<vector<int>> adjtrain(n+1);
	vector<vector<int>> adjroad(n+1);
	vector<int> dist(n+1,INT_MAX);
	for (int i = 0; i < m; i++) {
        int U, V;
        cin >> U >> V;
        adjtrain[U].push_back(V);
        adjtrain[V].push_back(U);
        is_rail[U][V] = is_rail[V][U] = true;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i != j && !is_rail[i][j]) {
                adjroad[i].push_back(j);
            }	
        }
    }
    
	if(is_rail[1][n] == true){
		dijkstra(1,adjroad,dist);
	}
	else
		dijkstra(1,adjtrain,dist);
	
	cout << (dist[n] == INT_MAX ? -1 : dist[n]);
}