結果

問題 No.3326 岩井星人の帰星
コンテスト
ユーザー 北杜
提出日時 2025-11-01 16:09:18
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 299 ms / 2,000 ms
コード長 1,801 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,491 ms
コンパイル使用メモリ 291,836 KB
実行使用メモリ 18,108 KB
最終ジャッジ日時 2025-11-01 16:09:34
合計ジャッジ時間 14,493 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 59
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// やけくそTLE解.

//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define all(a) (a).begin(), (a).end()
const ll INF32 = 2e9;
const ll INF64 = 4e18;

void printYN(bool ok){
    if(ok)cout << "Yes" << endl;
    else cout << "No" << endl;
    return;
}

signed main() {
    int N, M;
    cin >> N >> M;
    vector<vector<int>> G(N);
    rep(i, M){
        int u, v;
        cin >> u >> v;
        u--; v--;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    vector<int> kanshi(N, INF32);
    vector<bool> kakutei(N, false);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    int L;
    cin >> L;
    rep(i, L){
        int J, K;
        cin >> J >> K;
        J--;
        kanshi[J] = 1000-K;
        pq.push({1000-K,J});
    }
    while(!pq.empty()){
        int pos = pq.top().second; pq.pop();
        if(kakutei[pos])continue;
        kakutei[pos] = true;
        rep(i, G[pos].size()){
            int nex = G[pos][i];
            if(kanshi[nex]>kanshi[pos]+1){
                kanshi[nex]=kanshi[pos]+1;
                pq.push({kanshi[nex], nex});
            }
        }
    }
    queue<int> q;
    vector<int> dist(N, INF32);
    dist[0] = 0;
    if(kanshi[0]<=1000){
        printYN(0);
        return 0;
    }
    q.push(0);
    while(!q.empty()){
        int pos = q.front(); q.pop();
        rep(i, G[pos].size()){
            int nex = G[pos][i];
            if(dist[nex]!=INF32)continue;
            if(kanshi[nex]<=1000)continue;
            dist[nex] = dist[pos]+1;
            q.push(nex);
        }
    }
    if(dist[N-1]==INF32)printYN(0);
    else {
        printYN(1);
        cout << dist[N-1] << endl;
    }
    return 0;
}
0