Submission

Score: 100

User: Ninstroyer

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

Language: cpp

Time: 0.042 second

Submitted On: 2025-12-28 21:03:59

#include<bits/stdc++.h>
using namespace std;
#define int long long
int nx = 405, inf = 1e9;

vector<int> Dijkstra(vector<vector<pair<int,int>>>& adj, int start)
{
    vector<int> dist(nx, inf);
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    dist[start] = 0;
    pq.push({0,start});
    while(!pq.empty())
    {
        auto [curW, u] = pq.top();
        pq.pop();
        if(curW > dist[u]) continue;
        for(auto [v, w] : adj[u])
        {
            if(curW + w < dist[v])
            {
                dist[v] = curW + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

signed main()
{
    // 1 = train, 2 = bus
    int n, m; cin>>n>>m;
    vector<vector<pair<int,int>>> adj(nx);
    vector<vector<pair<int,int>>> bus(nx);
    vector<vector<bool>> train(nx,vector<bool>(nx,false));
    for(int i = 0; i < m; i++)
    {
        int u,v; cin>>u>>v;
        int d = abs(u-v)*10;
        adj[u].push_back({v,d});
        adj[v].push_back({u,d});
        train[u][v] = true;
        train[v][u] = true;
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(i==j) continue;
            if(!train[i][j])
            {
                int d = 10 * abs(i-j);
                bus[i].push_back({j,d});
            }
        }
    }

    vector<int> distBus = Dijkstra(bus, 1);
    vector<int> distTrain = Dijkstra(adj, 1);

    if(distBus[n] == inf || distTrain[n] == inf) return cout<<-1, 0;
    cout<<max(distBus[n], distTrain[n]);
}