結果

問題 No.3263 違法な散歩道
コンテスト
ユーザー syoyudango
提出日時 2025-10-20 04:14:37
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 169 ms / 2,000 ms
コード長 1,286 bytes
コンパイル時間 6,695 ms
コンパイル使用メモリ 288,568 KB
実行使用メモリ 14,720 KB
最終ジャッジ日時 2025-10-20 04:14:54
合計ジャッジ時間 9,572 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

int main() {
    const int INF = 1 << 30;
    int N, M;
    cin >> N >> M;
    vector<vector<int>> G(N);
    for (int i = 0; i < M; i++) {
        int U, V;
        cin >> U >> V;
        U--, V--;
        G[U].push_back(V), G[V].push_back(U);
    }
    int K;
    cin >> K;
    vector<bool> iwai(N);
    for (int i = 0; i < K; i++) {
        int A;
        cin >> A;
        A--;
        iwai[A] = true;
    }
    vector<vector<int>> dis(N, vector<int>(5, INF));
    queue<pair<int, int>> q;
    dis[0][0] = 0;
    q.emplace(0, 0);
    while (!q.empty()) {
        auto[v, t] = q.front();
        q.pop();
        for (int nv: G[v]) {
            if (iwai[nv]) {
                if (t <= 3 && dis[nv][t + 1] == INF) {
                    dis[nv][t + 1] = dis[v][t] + 1;
                    q.emplace(nv, t + 1);
                }
            } else {
                if (dis[nv][0] == INF) {
                    dis[nv][0] = dis[v][t] + 1;
                    q.emplace(nv, 0);
                }
            }
        }
    }
    if (*min_element(dis[N - 1].begin(), dis[N - 1].end()) == INF) {
        cout << -1 << endl;
    } else {
        cout << *min_element(dis[N - 1].begin(), dis[N - 1].end()) << endl;   
    }
    return 0;
}
0