Submission

Score: 100

User: Dormon

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

Language: cpp

Time: 0.039 second

Submitted On: 2025-03-15 20:26:54

#include <iostream>
#include <vector>
#include <queue>
#include <functional>

using namespace std;

template<typename A, typename B> ostream& operator << (ostream &out, pair<A, B> a){
    out << '{' << a.first << ", " << a.second << '}';
    return out;
}

template<typename T> ostream& operator << (ostream &out, vector<T> v){
    for (auto e:v)
        out << e << ' ';
    return out;
}

int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> adj1(n + 1), adj2(n + 1);
    vector<vector<bool>> vis(n + 1, vector<bool>(n + 1, false));
    for (int i = 0;i < m;i++){
        int u, v, w;
        cin >> u >> v;
        adj1[u].push_back({v, 10 * abs(u - v)});
        adj1[v].push_back({u, 10 * abs(u - v)});
        vis[u][v] = vis[v][u] = true;
    }

    for (int i = 1;i <= n;i++)
        for (int j = i + 1;j <= n;j++)
            if (!vis[i][j]){
                adj2[i].push_back({j, 10 * abs(i - j)});   
                adj2[j].push_back({i, 10 * abs(i - j)});
            }

    struct heap {
        int u, w;
        bool operator < (const heap &o) const {
            return w > o.w;
        }
    };
    
    vector<int> dist1(n + 1, 1e9), dist2(n + 1, 1e9);

    auto dijkstra = [&](vector<vector<pair<int, int>>> adj, vector<int> &dist, int u) -> void {
        priority_queue<heap> pq;
        pq.push({u, 0});
        while (!pq.empty()){
            auto [u, W] = pq.top(); pq.pop();
            if (dist[u] <= W) continue;
            dist[u] = W;
            for (auto [v, w]:adj[u])
                pq.push({v, W + w});
        }
    };
    dijkstra(adj1, dist1, 1);
    dijkstra(adj2, dist2, 1);

    // cout << "dist1 : " << dist1 << '\n';
    // cout << "dist2 : " << dist2 << '\n';

    // for (int i = 1;i <= n;i++)
    //     cout << "adj1[" << i << "] = " << adj1[i] << '\n';
    // for (int i = 1;i <= n;i++)
    //     cout << "adj2[" << i << "] = " << adj2[i] << '\n';

    if (dist1[n] == 1e9 || dist2[n] == 1e9)
        cout << "-1\n";
    else
        cout << max(dist1[n], dist2[n]) << '\n';
}