Submission

Score: 100

User: Test

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

Language: cpp

Time: 0.011 second

Submitted On: 2026-03-06 17:32:04

#include<bits/stdc++.h>
using namespace std;
//16.52-
int INF = 1e9;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,e;
    cin >> n >> e;
    vector<vector<pair<int,int>>> adj(n+1);
    vector<vector<char>> adj2(n+1,vector<char>(n+1,'R'));
    for(int i=0;i<n;i++) adj2[i][i]='X';
    for(int i=0;i<e;i++){
        int u,v;
        cin >> u >> v;
        int w = 10*abs(u-v);
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});

        adj2[u][v]='T';
        adj2[v][u]='T';
    }
    vector<vector<pair<int,int>>> adj3(n+1);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(adj2[i][j]=='R'){
                int w = 10*abs(i-j);
                adj3[i].push_back({j,w});
                adj3[j].push_back({i,w});
            }
        }
    }
    //--------------------------------
    vector<int>dist(n+1,INF);
    priority_queue<pair<int,int>,vector<pair<int,int>>, greater<pair<int,int>>> pq;

    dist[1] = 0;
    pq.push({0,1});

    while(!pq.empty()){
        int du = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if(du>dist[u]) continue;

        for(auto &[v,w] : adj[u]){
            if(du+w<dist[v]){
                dist[v]=du+w;
                pq.push({dist[v],v});
            }
        }
    }
    //--------------------------------
    vector<int>dist3(n+1,INF);
    priority_queue<pair<int,int>,vector<pair<int,int>>, greater<pair<int,int>>> pq3;

    dist3[1] = 0;
    pq3.push({0,1});

    while(!pq3.empty()){
        int du = pq3.top().first;
        int u = pq3.top().second;
        pq3.pop();

        if(du>dist3[u]) continue;

        for(auto &[v,w] : adj3[u]){
            if(du+w<dist3[v]){
                dist3[v]=du+w;
                pq3.push({dist3[v],v});
            }
        }
    }
    //cout << dist[n] << " " << dist3[n];
    if(max(dist[n],dist3[n])==INF) cout << -1;
    else cout << max(dist[n],dist3[n]);

}