結果

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

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <array>
#include <queue>
using namespace std;
constexpr int INF = 1070000000;
# pragma GCC optimize("O3")
int main(void){
    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;
    bool A[N] = {};
    for (int i = 0; i < K; i++)
    {
        int tmp;
        cin >> tmp;
        tmp--;
        A[tmp] = true;
    }
    int dp[N][5];
    for (int i = 0; i < N; i++)
        for (int j = 0; j < 5; j++)
            dp[i][j] = INF;
     dp[0][0] = 0;
     queue<array<int, 2>> q;
     q.push({0, 0});
     while (not q.empty())
     {
         const array<int, 2> now = q.front();
         q.pop();
         for (int i : G[now[0]]) {
             const int j = A[i] ? now[1] + 1 : 0;
             if (j < 5 && dp[now[0]][now[1]] + 1 < dp[i][j])
             {
                 dp[i][j] = dp[now[0]][now[1]] + 1;
                 if (i == N - 1)
                 {
                     cout << dp[i][j] << '\n';
                     return 0;
                 }
                 q.push({i, j});
             }
         }
     }
     cout << -1 << '\n';
}
0