Submission

Score: 0

User: fillhavertz

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

Language: cpp

Time: 0.002 second

Submitted On: 2025-10-14 11:29:07

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    vector<vector<int>> trainGraph(N + 1);

    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        trainGraph[u].push_back(v);
        trainGraph[v].push_back(u);
    }

    // BFS: (car, train)
    vector<vector<int>> dist(N + 1, vector<int>(N + 1, -1));
    queue<pair<int,int>> q;
    q.push({1,1});
    dist[1][1] = 0;

    while (!q.empty()) {
        auto [car, train] = q.front();
        q.pop();

        // ??Ҷ֧???ͧ N ??駤??????
        if (car == N && train == N) {
            cout << dist[car][train] * 10 << "\n";
            return 0;
        }

        // ö¹?????????ͧ???
        for (int nextCar = 1; nextCar <= N; nextCar++) {
            if (nextCar == car) continue;

            // ö?????ö????ͧ?????????Ѻ train
            for (int nextTrain : trainGraph[train]) {
                // ??????ҵç?ѹ (?Թ??????ѹ)
                if (abs(nextCar - car) == 1) { // ????ö??????? 10 ??????
                    if (dist[nextCar][nextTrain] == -1) {
                        dist[nextCar][nextTrain] = dist[car][train] + 1;
                        q.push({nextCar, nextTrain});
                    }
                }
            }
        }
    }

    cout << -1 << "\n";
    return 0;
}