結果

問題 No.3263 違法な散歩道
ユーザー yt142857
提出日時 2025-09-06 13:45:27
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 4,035 bytes
コンパイル時間 2,460 ms
コンパイル使用メモリ 214,128 KB
実行使用メモリ 159,164 KB
最終ジャッジ日時 2025-09-06 13:45:47
合計ジャッジ時間 8,851 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 TLE * 1 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*
n,m = map(int,input().split())
graph = {}
for i in range(n):
  graph[i+1] = []
for i in range(m):
  a,b = map(int,input().split())
  graph[a].append(b)
  graph[b].append(a)
iwai_num = int(input())
if iwai_num != 0:
  iwai = [int(_) for _ in input().split()]
else:
  iwai = []
iwai = set(iwai)
non_iwai = []
for i in range(1,n+1):
  if i not in iwai:
    non_iwai.append(i)
graph2 = {}
for i in range(n):
  graph2[i+1] = []
from collections import deque
for i in non_iwai:
  queue = deque()
  queue.append((i,0))
  visited = set()
  visited.add(i)
  ok = []
  while queue:
    node,dis = queue.popleft()
    if dis > 5:
      break
    if node not in iwai:
      ok.append((node,dis))
    for nei in graph[node]:
      if nei not in visited:
        visited.add(nei)
        queue.append((nei,dis+1))
  for j,dis in ok:
    if i != j:
      graph2[i].append((dis,j))
import heapq
kakutei = [False]*(n+1)
heap = [(0,1)]
cur = [float('inf')]*(n+1)
cur[1] = 0
while heap:
  n_dis,node = heapq.heappop(heap)
  if kakutei[node]:
    continue
  kakutei[node] = True
  for n_dis,nei in graph2[node]:
    if cur[node]+n_dis < cur[nei]: 
      heapq.heappush(heap,(cur[node]+n_dis,nei))
      cur[nei] = cur[node]+n_dis
if cur[n] == float('inf'):
  cur[n] = -1
print(cur[n])
*/

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<int>> graph(n + 1);
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    int iwai_num;
    cin >> iwai_num;
    vector<bool> is_iwai(n + 1, false);
    if (iwai_num != 0) {
        for (int i = 0; i < iwai_num; ++i) {
            int x; cin >> x;
            if (1 <= x && x <= n) is_iwai[x] = true;
        }
    }
    // Build list of non-iwai nodes (1-based)
    vector<int> non_iwai;
    non_iwai.reserve(n);
    for (int i = 1; i <= n; ++i) {
        if (!is_iwai[i]) non_iwai.push_back(i);
    }

    // graph2: for each node i (1..n) store pairs (weight, neighbor) matching Python semantics
    vector<vector<pair<int,int>>> graph2(n + 1);

    // BFS up to distance 5 from each non_iwai node
    for (int start : non_iwai) {
        deque<pair<int,int>> q;
        q.emplace_back(start, 0);
        vector<char> visited(n + 1, false);
        visited[start] = true;
        vector<pair<int,int>> ok; // (node, dist)
        while (!q.empty()) {
            auto [node, dist] = q.front();
            q.pop_front();
            if (dist > 5) break; // same logic as Python (break completely when pop dist>5)
            if (!is_iwai[node]) {
                ok.emplace_back(node, dist);
            }
            for (int nei : graph[node]) {
                if (!visited[nei]) {
                    visited[nei] = true;
                    q.emplace_back(nei, dist + 1);
                }
            }
        }
        for (auto &p : ok) {
            int j = p.first;
            int d = p.second;
            if (start != j) {
                // store as (weight, neighbor) to match Python's (dis, j)
                graph2[start].emplace_back(d, j);
            }
        }
    }

    // Dijkstra on graph2 from node 1 to node n
    const int INF = 1e9;
    vector<int> cur(n + 1, INF);
    vector<char> confirmed(n + 1, false);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    cur[1] = 0;
    pq.emplace(0, 1);
    while (!pq.empty()) {
        auto [dist, node] = pq.top();
        pq.pop();
        if (confirmed[node]) continue;
        confirmed[node] = true;
        for (auto &edge : graph2[node]) {
            int w = edge.first;
            int nei = edge.second;
            if (cur[node] + w < cur[nei]) {
                cur[nei] = cur[node] + w;
                pq.emplace(cur[nei], nei);
            }
        }
    }

    if (cur[n] == INF) cout << -1 << "\n";
    else cout << cur[n] << "\n";

    return 0;
}
0