Codeforces #816 (Div. 2) E. Long Way Home 1週間考えても分からなかった orz
陸路だけのグラフを考えると$ N頂点、$ N辺なのでダイクストラ法で$ O(N \log N)で解ける。空路は$ N^2辺あるので、単純に辺を足すとオーダーが$ O(N^2 \log N)になって間に合わない。 ここで、次のように考える。まず$ K = 1とする。まずは飛行機を使わずに陸路のみで都市$ 1から各都市までの最短距離をダイクストラ法で計算する。これで$ K = 0の場合の最短距離$ d_iが求まる。つぎにこのあとに空路を$ 1回だけ使うと、最短距離はつぎのように更新される。
$ d_i' = \min_j d_j + \left(i - j\right)^2
さらに、この得られた$ d_i'についてダイクストラ法を実行すれば、$ K = 1の場合の最短距離が求まる。同様に$ K = kについて$ d_iが求まったら同じことを行って$ K = k + 1の場合の最短距離が求まる。
ここで、空路を考慮に入れて更新する操作は単純に実装すると$ O(N^2)になるので、何らかの工夫が必要になる。ここで空路のコストが$ \left(i - j\right)^2であることからConvex Hull Trickを使う。上記の$ d_i'の更新式を展開するとつぎのようになる。 $ \begin{aligned} d_i' &= \min_j d_j + \left(i - j\right)^2 \\ &= i^2 + \min_j \left(-2ji + j^2 + d_j\right) \end{aligned}
この第2項は$ -2jx + j^2 + d_j\quad(1 \le j \le n)で表される直線群で構成される凸包の$ x = iでの値になる。$ d_i'は任意の順番で計算できるので、$ iの小さい方から順番に計算すればよい。また直線の追加はとくに縛りがないので最初にぜんぶ追加する。
実装はつぎのようになる。なおdistの初期値を適当に$ 10^{15}にしたら直線の交点を計算する式で傾きと切片の乗算でオーバーフローが発生したので$ 10^{12}に直した orz 傾きが$ 10^5で切片が$ distのオーダーになるので、乗算したときに$ 10^{18}を超えないようにする必要がある。
code:java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) {
FastScanner scanner = new FastScanner();
int n = scanner.nextInt();
int m = scanner.nextInt();
int k = scanner.nextInt();
List<Edge>[] graph = new Listn; for (int i = 0; i < n; i++) graphi = new ArrayList<>(); for (int i = 0; i < m; i++) {
int x = scanner.nextInt() - 1;
int y = scanner.nextInt() - 1;
long c = scanner.nextLong();
graphx.add(new Edge(y, c)); graphy.add(new Edge(x, c)); }
long[] dist = solve(graph, n, k);
for (int i = 0; i < n; i++) {
System.out.print(disti + " "); }
System.out.println();
}
private static long[] solve(List<Edge>[] graph, int n, int K) {
for (int i = 0; i < n; i++) disti = 1_000_000_000_000L; djkstra(graph, n, dist);
for (int k = 0; k < K; k++) {
// Update dist assuming a flight between any pair of cities can be done
updateWithFlight(n, dist);
djkstra(graph, n, dist);
}
return dist;
}
private static void updateWithFlight(int n, long[] dist) {
Deque<Line> deque = new LinkedList<>();
for (int i = 0; i < n; i++) {
Line f3 = new Line((long) -2 * (i + 1), (long) (i + 1) * (i + 1) + disti); while (deque.size() > 1) {
Line f2 = deque.removeFirst();
Line f1 = deque.peekFirst();
if ((f2.a - f1.a) * (f3.b - f2.b) < (f3.a - f2.a) * (f2.b - f1.b)) {
deque.addFirst(f2);
break;
}
}
deque.addFirst(f3);
}
for (int i = 0; i < n; i++) {
while (deque.size() > 1) {
Line last = deque.removeLast();
if (deque.peekLast().y(i + 1) > last.y(i + 1)) {
deque.addLast(last);
break;
}
}
disti = Math.min(disti, deque.peekLast().y(i + 1) + (long) (i + 1) * (i + 1)); }
}
private static void djkstra(List<Edge>[] graph, int n, long[] dist) {
PriorityQueue<Node> toVisit = new PriorityQueue<>(Comparator.comparingLong(o -> o.dist));
for (int i = 0; i < n; i++) {
toVisit.add(new Node(i, disti)); }
while (!toVisit.isEmpty()) {
Node candidate = toVisit.remove();
int from = candidate.id;
for (Edge e : graphfrom) { int next = e.to;
long cost = e.cost;
long newValue = distfrom + cost; if (distnext > newValue) { toVisit.add(new Node(next, newValue));
}
}
}
}
private static class Line {
private final long a;
private final long b;
private Line(long a, long b) {
this.a = a;
this.b = b;
}
public long y(int x) {
return a * x + b;
}
}
private static class Node {
private final int id;
private final long dist;
private Node(int id, long dist) {
this.id = id;
this.dist = dist;
}
}
private static class Edge {
private final int to;
private final long cost;
private Edge(int to, long cost) {
this.to = to;
this.cost = cost;
}
}
}