[JOI精進録] 難易度7「ゾンビ島」(第15回日本情報オリンピック 予選E)

問題リンク

atcoder.jp

問題概要

頂点辺の無向グラフが与えられる。
そのうち個の頂点に訪れる事はできない。
また、それらの頂点から本以下の辺を通って移動できる頂点へ訪れるときは重みがかかる。
それ以外の頂点へ訪れるときは重みがかかる。ただし頂点に訪れるときに重みはかからない。
頂点1から出発し頂点を訪れるとき重みの総和の最小値を求めなさい。

解説

AC解法 (100/100点)

BFSを使って危険な街を列挙し、Dijkstra法を使って宿泊費の総和の最小値を求める。
またBFSをK頂点毎に行うのは重いため超頂点というテクニックを使って1回にまとめる。

ACコード

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

int main(){
#define int long long
  int n,m,k,s; cin >> n >> m >> k >> s;
  int p,q,a,b; cin >> p >> q;
  vector<int> dist(n),res(n); queue<int> que; int t;
  for (int i(0);i < k;++i) (cin >> a),--a,dist[a]=1,que.emplace(a);
  vector<vector<int>> G(n); for (int i(0);i < m;++i) (cin>>a>>b),--a,--b,G[a].emplace_back(b),G[b].emplace_back(a);
  while(!que.empty()){
    int t = que.front(); que.pop();
    if (dist[t]==s+1) break;
    for (int a:G[t]){
      if (dist[a]) continue;
      dist[a]=dist[t]+1,que.emplace(a);
    }
  }
  set<pair<int,int>> pque; pque.emplace(0,0),dist[n-1]=0;
  while(!pque.empty()){
    auto [a,b] = *pque.begin(); pque.erase(pque.begin());
    if (b==n-1) break;
    if (a!=res[b]) continue;
    for (int c:G[b]){
      if (dist[c]==1) continue;
      int d = res[b]+(dist[c]?q:p);
      if (res[c]&&res[c]<=d) continue;
      res[c]=d,pque.emplace(d,c);
    }
  }
  cout << res[n-1]-p << endl;
}

提出結果

atcoder.jp