RUPC2018 day2 E: Light - ferinの競プロ帳

解法

拡張dijkstraをする。頂点を(i番目の街灯,コストj)とする。
遷移について

始点から街灯
始点と街灯のマンハッタン距離のコストをかけて街灯を明るくする必要がある
街灯から終点
街灯と終点のマンハッタン距離のコスト分 - すでに街灯が明るくなっている距離の分のコストが必要
街灯から街灯
街灯と街灯のマンハッタン距離のコスト分 - すでに街灯が明るくなっている距離の分 - 1 のコストが必要
到着する方の街灯があるマスはすでに明るいためマイナス1するべき

あとはコストがマイナスになってはおかしいので下限を0で抑える必要があるのに注意
街灯から街灯への遷移で愚直にやるとO(N(H+W))かかるが、届かないコストで明るくしても移動できないし必要以上に明るくしても無駄なので遷移先の街灯のコストは1種類に決められる。したがって遷移先はO(N)種類で抑えられる。

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int x[105], y[105];
int d[105][1010];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int w, h, n;
  cin >> w >> h >> n;
  REP(i, n) {
    cin >> x[i] >> y[i];
    x[i]--, y[i]--;
  }

  REP(i, 105) REP(j, 1010) d[i][j] = LLINF;
  priority_queue<VI, VVI, greater<VI>> que;
  // スタート地点から街灯iに向かう
  REP(i, n) {
    int cost = x[i]+y[i];
    d[i][cost] = cost;
    que.push({cost, i, cost});
  }

  while(que.size()) {
    VI v = que.top(); que.pop();
    int dist = v[0], idx = v[1], cost = v[2];
    if(dist > d[idx][cost]) continue;
    REP(i, n) {
      if(idx == i) continue;
      int n_cost = max(0LL, abs(x[idx]-x[i]) + abs(y[idx]-y[i]) - cost - 1);
      if(d[i][n_cost] > d[idx][cost] + n_cost) {
        d[i][n_cost] = d[idx][cost] + n_cost;
        que.push({d[i][n_cost], i, n_cost});
      }
    }
  }

  int ans = LLINF;
  REP(i, n) REP(j, 1010) {
    chmin(ans, d[i][j] + max(0LL, abs(w-1-x[i]) + abs(h-1-y[i]) - j));
  }
  cout << ans << endl;

  return 0;
}