AOJ1178 壊れたドア & ドワコン16予選c「メンテナンス明け
ダイクストラ法の練習ということで。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1178&lang=jp
まずは壊れたドアから。
グリッドグラフで、どこか一箇所のドアが壊れたときの最悪時間が最短となるような経路を求めろ、という問題。
まず、全部のドアについて、そのドアが壊れた時のゴール対全てのドアの最短距離を計算しておきます。そして、再びゴールから辿って行くと、あるドアAを通って部屋Bに遷移するとき、
・Aが壊れたときの、ゴールからBまでの距離
・ふつうの距離
の二通りで大きい方で遷移させます。これをダイクストラ法と同じようにまわしてあげると答えが求まる、という寸法。発想としてはそんなに難しくはない気がしますが、バグらせやすくて大変でした。
int H, W; struct Edge { int num, to; Edge(int n, int t) : num(n), to(t) {}}; vector<vector<Edge>> edges; bool bfs(int broken_edge, vector<int>& dist) { dist[(H - 1) * W + W - 1] = 0; queue<int> que; que.push((H - 1) * W + W - 1); while(!que.empty()) { int cur = que.front(); que.pop(); for(const Edge& e : edges[cur]) { if(e.num == broken_edge || dist[e.to] != INF) continue; dist[e.to] = dist[cur] + 1; que.push(e.to); } } return dist[0] == INF; } int solve(const vector<vector<int>>& wdist) { vector<int> dist(H * W, INF); priority_queue<pint, vector<pint>, greater<pint>> que; dist[(H - 1) * W + W - 1] = 0; que.emplace(0, (H - 1) * W + W - 1); auto upd = [](int& a, int b) { return a > b ? (a = b, true) : false;}; while(!que.empty()) { int cos, node; tie(cos, node) = que.top(); que.pop(); if(dist[node] < cos) continue; for(const Edge& e : edges[node]) { int ncos = max(cos + 1, wdist[e.num][e.to]); if(upd(dist[e.to], ncos)) que.emplace(ncos, e.to); } } return dist[0]; } int main() { cin.tie(0); ios::sync_with_stdio(false); while(cin >> H >> W && H) { int t_, edgenum = 0; edges.assign(H * W, vector<Edge>()); rep(i, H) { rep(j, W - 1) { cin >> t_; if(t_ == 0) { edges[i * W + j].emplace_back(edgenum, i * W + j + 1); edges[i * W + j + 1].emplace_back(edgenum, i * W + j); ++edgenum; } } if(i == H - 1) continue; rep(j, W) { cin >> t_; if(t_ == 0) { edges[i * W + j].emplace_back(edgenum, (i + 1) * W + j); edges[(i + 1) * W + j].emplace_back(edgenum, i * W + j); ++edgenum; } } } vector<vector<int>> wdist(edgenum, vector<int>(H * W, INF)); rep(i, edgenum) if(bfs(i, wdist[i])) goto fail; cout << solve(wdist) << endl; continue; fail: cout << "-1" << endl; } return 0; }
http://dwango2016-prelims.contest.atcoder.jp/tasks/dwango2016qual_c
次はこれ。電車で寝過ごして終点まで行ってしまうかもしれないときの最適経路の最悪時間を答える問題。
とりあえず普通に、ある辺について終点とそこまでのコストを持たせてみたのですが、遷移がうまくいかず……。
そこで逆辺の終点とそこまでのコストを持たせて、後ろから
・普通にそこまでのコスト+辺のコスト
・終点まで行って、戻ってくるコスト
の大きい方をdistの候補にする、みたいにやると、うまいことシュミレーションできました。
#include <bits/stdc++.h> using namespace std; const int INF = 1000000000; #define REP(i,s,n) for(int i=(int)(s);i<(int)(n);++i) #define rep(i,n) REP(i, 0, n) typedef long long int i64; typedef pair<int, int> pint; struct Edge { int to, cost, terminal, wcost; //逆辺の終点と終点までのコストを入れる Edge(int t, int c, int te, int w) : to(t), cost(c), terminal(te), wcost(w) {} }; bool upd(int& a, int b) { return a > b ? (a = b, true) : false;}; vector<Edge> edges[25252]; vector<int> setdist(int N, int G) { vector<int> dist(N, INF); dist[G] = 0; priority_queue<pint, vector<pint>, greater<pint>> que; que.push(pint(0, G)); while(!que.empty()) { int cos, ver; tie(cos, ver) = que.top(); que.pop(); if(cos > dist[ver]) continue; for(const Edge& e : edges[ver]) if(upd(dist[e.to], cos + e.cost)) que.push(pint(dist[e.to], e.to); } return dist; } int main() { cin.tie(0); ios::sync_with_stdio(false); int N, M, S, G; cin >> N >> M >> S >> G; rep(_, M) { int lnum; cin >> lnum; vector<int> l(lnum), w(lnum - 1); rep(i, lnum) cin >> l[i]; rep(i, lnum - 1) cin >> w[i]; int sum = accumulate(w.begin(), w.end(), 0); int cosum = 0; rep(i, lnum - 1) { edges[l[i]].push_back(Edge(l[i + 1], w[i], l.front(), cosum)); edges[l[i + 1]].push_back(Edge(l[i], w[i], l.back(), sum - cosum)); cosum += w[i]; } } vector<int> dist = setdist(N, G); priority_queue<pint, vector<pint>, greater<pint>> que; que.push(pint(0, G)); vector<int> wdist(N, INF); wdist[G] = 0; while(!que.empty()) { int cos, ver; tie(cos, ver) = que.top(); que.pop(); if(cos > wdist[ver]) continue; for(const auto& e : edges[ver]) { int wcos = dist[e.terminal] + e.wcost; int ncos = cos + e.cost; int max_cos = max(wcos, ncos); if(upd(wdist[e.to], max_cos)) que.push(pint(wdist[e.to], e.to)); } } cout << wdist[S] << endl; return 0; }
逆辺の情報をもたせるところが面白いと思いました。想定解かどうかは知りませんが……。