結果

問題 No.3263 違法な散歩道
コンテスト
ユーザー l33t
提出日時 2025-09-08 02:54:10
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 242 ms / 2,000 ms
コード長 1,375 bytes
コンパイル時間 4,266 ms
コンパイル使用メモリ 291,556 KB
実行使用メモリ 18,436 KB
最終ジャッジ日時 2025-09-08 02:54:20
合計ジャッジ時間 8,314 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(obj) (obj).begin(), (obj).end()
using ll = long long;
using namespace std;

int main() {
    int N,M,K;cin>>N>>M;
    vector<vector<int>> gr(N);
    rep(i,M){
        int u,v;cin>>u>>v;
        u--;v--;
        gr[u].push_back(v);
        gr[v].push_back(u);
    }
    cin>>K;
    set<int> A;
    rep(i,K){
        int a;cin>>a;
        A.insert(a-1);
    }

    const ll INF =1e12 ;
    vector<vector<ll>> seen(N,vector<ll>(5,INF));
    seen[0][0] = 0;
    queue<pair<int,int>> qu;
    qu.push({0,0});
    seen[0][0] = 0;
    while(!qu.empty()){
        auto [crnt,met] = qu.front();
        qu.pop();

        for(int nx:gr[crnt]){
            bool isiwi = (A.count(nx)==1);
            if(!isiwi){
                if( seen[nx][0] == INF){
                    seen[nx][0] = seen[crnt][met]+1;
                    qu.push({nx,0});
                }
            }else{
                if( met == 4) continue;
                if( seen[nx][met+1]==INF){
                    seen[nx][met+1] = seen[crnt][met]+1;
                    qu.push({nx,met+1});
                }
            }
        }
    }
    ll ans = INF;
    for(int i = 0; i <5; i++){
        ans = min(ans,seen[N-1][i]);
    }
    if(ans == INF){
        cout << -1 << endl;
    }else{
        cout << ans << endl;
    }
}
0