第2回 ドワンゴからの挑戦状 予選 C - メンテナンス明け
解けず。この手の二分法を思い付くのまだ苦手。
C - メンテナンス明け
解説
移動時間の制限を決めると、寝過しの発生が辺の使用の制約に変わるので、これで二分探索。
実装
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
typedef long long ll;
using namespace std;
struct edge_t { int to; ll cost; int terminal; ll cost_to_terminal; };
struct state_t { int i; ll cost; };
bool operator < (state_t a, state_t b) { return a.cost > b.cost; }
int main() {
int n, m, src, dst; cin >> n >> m >> src >> dst;
vector<vector<edge_t> > g(n);
repeat (i,m) {
int l; cin >> l;
vector<int> s(l); repeat (j,l) cin >> s[j];
vector<ll> w(l-1); repeat (j,l-1) cin >> w[j];
ll total = accumulate(w.begin(), w.end(), 0ll);
ll acc = 0;
repeat (j,l-1) {
g[s[j ]].push_back((edge_t) { s[j+1], w[j], s.back(), total-acc });
acc += w[j];
g[s[j+1]].push_back((edge_t) { s[j ], w[j], s.front(), acc });
}
}
vector<ll> dist(n, -1); {
priority_queue<state_t> q; // dijkstra from dst
q.push((state_t) { dst, 0 });
while (not q.empty()) {
state_t s = q.top(); q.pop();
if (dist[s.i] != -1) continue;
dist[s.i] = s.cost;
for (edge_t e : g[s.i]) if (dist[e.to] == -1) {
q.push((state_t) { e.to, s.cost + e.cost });
}
}
}
ll low = -1, high = 1e18; // (low, high]
while (low + 1 < high) { // binary-search
ll mid = (low + high) / 2;
vector<ll> sdist(n, -1);
priority_queue<state_t> q; // dijkstra from src
q.push((state_t) { src, 0 });
while (not q.empty()) {
state_t s = q.top(); q.pop();
if (sdist[s.i] != -1) continue;
sdist[s.i] = s.cost;
if (s.i == dst) break;
for (edge_t e : g[s.i]) if (sdist[e.to] == -1) {
if (s.cost + e.cost_to_terminal + dist[e.terminal] <= mid) { // NESUGOSHI
q.push((state_t) { e.to, s.cost + e.cost });
}
}
}
(sdist[dst] == -1 ? low : high) = mid;
}
cout << high << endl;
return 0;
}