結果

問題 No.3263 違法な散歩道
コンテスト
ユーザー iastm
提出日時 2025-09-06 13:39:32
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 149 ms / 2,000 ms
コード長 1,208 bytes
コンパイル時間 1,080 ms
コンパイル使用メモリ 106,504 KB
実行使用メモリ 15,488 KB
最終ジャッジ日時 2025-09-06 13:40:09
合計ジャッジ時間 4,944 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <array>
#include <queue>

int main() {
    int N, M;
    std::cin >> N >> M;
    std::vector<std::vector<int>> graph(N);
    while (M--) {
        int U, V;
        std::cin >> U >> V;
        U--, V--;
        graph[U].emplace_back(V);
        graph[V].emplace_back(U);
    }
    std::vector<bool> has_yiwiy9(N);
    int K;
    std::cin >> K;
    while (K--) {
        int A;
        std::cin >> A;
        A--;
        has_yiwiy9[A] = true;
    }

    std::vector<std::vector<int>> dist(N, std::vector<int>(5, -1));
    std::queue<std::array<int, 3>> queue;
    queue.push({0, 0, 0});

    while (queue.size()) {
        auto [u, d, n] = queue.front();
        queue.pop();
        if (dist[u][d] != -1) continue;
        dist[u][d] = n;
        for (int v : graph[u]) {
            int nd = has_yiwiy9[v] ? d + 1 : 0;
            if (nd == 5) continue;
            if (dist[v][nd] != -1) continue;
            queue.push({v, nd, n + 1});
        }
    }

    int result = -1;
    for (int d = 0; d < 5; d++) {
        if (result == -1 || dist[N - 1][d] != -1 && result > dist[N - 1][d]) result = dist[N - 1][d];
    }
    std::cout << result << std::endl;
}
0