Submission

Score: 100

User: theem1502

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

Language: cpp

Time: 0.022 second

Submitted On: 2026-02-17 13:34:03

#include <bits/stdc++.h>
using namespace std;
int v;
const int INF = 1e9;
int bfs(vector<vector<pair<int,int>>> &adjlist) {
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> theq;
    theq.push(make_pair(0, 1));
    vector<int> dist(v+1, INF);
  //  vector<bool> visited(v+1, false);
    while(!theq.empty()) {
        int currentw = theq.top().first, currentv = theq.top().second;
        theq.pop();
        if (currentw > dist[currentv] /*|| visited[currentv]*/) {
            continue;
        }
       // visited[currentv] = true;
        for (auto [r, w]: adjlist[currentv]) {
            if (currentw + w < dist[r]) {
                dist[r] = currentw + w;
                theq.push(make_pair(dist[r], r));
            }



        }
    }

        return dist[v];


}



int intabs(int a) {
    if ( a < 0) {
        return -1 * a;

    }
    return a;
}


int main() {
    int u;
    cin >> v>> u;
    vector<vector<pair<int,int>>> adjlist(v+1);
    vector<vector<bool>> mapping(v+1, vector<bool> (v+1, false));
    for (int i = 0; i < u; i++) {
        int first, second;
        cin >> first >> second;
        adjlist[first].push_back(make_pair(second, intabs(second - first)));
        adjlist[second].push_back(make_pair(first, intabs(second-first)));
        mapping[first][second] = true;
        mapping[second][first] = true;

    }
    vector<vector<pair<int,int>>> revadj(v+1);

    for (int i = 1; i <= v; i++) {
        for (int j = 1; j <= v; j++) {
            if (i == j || mapping[i][j] || mapping[j][i]) {
                continue;
            }
            revadj[i].push_back(make_pair(j, intabs(j - i)));
            revadj[j].push_back(make_pair(i, intabs(j-i)));


        }
    }
/*
    for (int i = 1; i<= v; i++) {
            for (auto [x, y]: revadj[i]) {
                cout << x << " ";
            }
            cout << "\n";

    }

*/


//cout << "f";
    int val = bfs(adjlist);
    int secondval = bfs(revadj);
  //  cout << "theval: " << val << " " << secondval << "\n";
    //cout << "here";
    if (val == INF || secondval == INF) {
        cout << -1;
    }
    else {
        cout << max(val, secondval) * 10;
    }


}