square869120Contest #5 E - Broken Skateboard

問題ページ
最短路問題+の条件なので dist[マスi][k] = 最短経路 というような拡張dijkstraをすればよさそう．

• 個の各頂点を始点として拡張dijkstra
  コンクリートのマスの数を とすると
• 止まる頂点はコンクリートとゴールのマスのみ
  拡張dijkstraの頂点数，辺数を にできるので
• 始点はコンクリートのみ
  コンクリート以外のマスの答えは (最寄りのコンクリートまでの距離) + (そのコンクリートからゴールの距離) なので全マスからdijkstraしなくともよい．
• 終点からdijkstra
  多くの始点から1つの終点までの距離を求めるときに各始点からdijkstraをするのではなく，終点から1回dijkstraをすることで各頂点までの距離を求めることができる．
• DP
  dijkstraの遷移を考えると dist[i][j] → dist[to][j-1] となる．毎回jが1減り，jが増えるような遷移が存在しないためこのグラフはDAGである．したがってDPで最短経路を求めることができる．

DAGでlog落とせるのに気づかなかった…

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#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()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG_   
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
const ll INF = 1LL<<30;  
  
int main(void) {  
    ll h, w;  
    cin >> h >> w;  
    vector<string> s(h);  
    REP(i, h) cin >> s[i];  
  
    // コンクリートとゴールからなるグラフを作成  
    ll n = 0, gx = -1, gy = -1;  
    vector<vector<ll>> trans(h, vector<ll>(w, -1));  
    vector<PII> inv;  
    REP(i, h) REP(j, w) {  
        if(s[i][j] == '#') {  
            trans[i][j] = n++;  
            inv.push_back({i, j});  
        }  
        if(s[i][j] == 'G') gx = j, gy = i;  
    }  
    trans[gy][gx] = n++;  
    inv.push_back({gy, gx});  
  
    vector<vector<PII>> g(n);  
    REP(i, h) {  
        ll pre = -1;  
        REP(j, w) {  
            if(s[i][j] == '#' || s[i][j] == 'G') {  
                if(pre == -1) {  
                    pre = j;   
                    continue;  
                }  
                ll u = trans[i][pre], v = trans[i][j];  
                g[u].push_back({v, j-pre});  
                g[v].push_back({u, j-pre});  
                pre = j;  
            }  
        }  
    }  
    REP(i, w) {  
        ll pre = -1;  
        REP(j, h) {  
            if(s[j][i] == '#' || s[j][i] == 'G') {  
                if(pre == -1) {  
                    pre = j;  
                    continue;  
                }  
                ll u = trans[pre][i], v = trans[j][i];  
                g[u].push_back({v, j-pre});  
                g[v].push_back({u, j-pre});  
                pre = j;  
            }  
        }  
    }  
  
    // 終点からDPで最短距離を求める  
    vector<vector<ll>> dist(n+1, vector<ll>(n, INF));  
    REP(i, n+1) dist[i][trans[gy][gx]] = 0;  
    for(ll i=n; i>0; --i) {  
        REP(j, n) for(auto to: g[j]) {  
            chmin(dist[i-1][to.first], dist[i][j] + i*to.second);  
        }  
    }  
  
    // 氷のマスからスタートする場合  
    vector<vector<ll>> ans(h, vector<ll>(w, INF));  
    REP(i, n) {  
        ll x = inv[i].second, y = inv[i].first;  
        chmin(ans[y][x], dist[0][i]);  
        FOR(j, x+1, w) {  
            chmin(ans[y][j], dist[1][i] + j-x);  
            if(s[y][j] == '#' || s[y][j] == 'G') break;  
        }  
        FOR(j, y+1, h) {  
            chmin(ans[j][x], dist[1][i] + j-y);  
            if(s[j][x] == '#' || s[j][x] == 'G') break;  
        }  
        for(ll j=x-1; j>=0; --j) {  
            chmin(ans[y][j], dist[1][i] + x-j);  
            if(s[y][j] == '#' || s[y][j] == 'G') break;  
        }  
        for(ll j=y-1; j>=0; --j) {  
            chmin(ans[j][x], dist[1][i] + y-j);  
            if(s[j][x] == '#' || s[j][x] == 'G') break;  
        }  
    }  
  
    REP(i, h) REP(j, w) cout << (ans[i][j]==INF?-1:ans[i][j]) << (j==w-1?'\n':' ');  
    cout << flush;  
  
    return 0;  
}