#816 Div2E. Long Way Home 斜率优化dp

E. Long Way Home
斜率优化dp，dijkstra

题意

给定一个 $n$ 个点， $m$ 条边的带权无向图，边形如 $<u,v,w>$ ，起点为 $1$ 。可以乘坐至多 $k$ 次飞机，从 $u$ 到 $v$ ，距离为 $(u-v{)}^2$ 。求到每个点的最短距离。$(n,m\le 1e5,k\le 20)$

思路

当 $k=0$ 时，dijkstra即可求出最短路，考虑 $k=1$ 时如何求。
一个显而易见的做法是在 $k=0$ 的基础上，枚举哪两个点之间坐了飞机。

for(int i = 1; i <= n; i++) {
	for(int j = 1; j <= n; j++) {
		dis[i] = min(dis[i], old_dis[j] + (u - v)*(u - v));
	}
}	
1
2
3
4
5

当然，不一定是最后一步才坐飞机，所以更新 $dis$ 后仍需要跑一遍dijkstra，可以得到答案。
于是我们得到了 $O(k{n}^2)$ 的做法。
由于 $k$ 范围很小，给了我们提示：从 $0,1,2,...k-1$ 一直枚举到 $k$ ，所以考虑如何优化上述转移。
将上述转移写为数学表达式
$$dis[v]=mi{n}_{u\in [1,n]}(old\_dis[u]+(u-v{)}^2)=old\_dis[u]+u^2+v^2-2\times u\times v$$
上式中，因为有 $u\times v$ 的项，考虑斜率优化。
设 $k=-2u,b=old\_dis[u]+u^2,f(v)=kv+b$ ，则原式转化为 $dis[v]=f(v)+v^2$ 。
其中 $f(v)$ 即为所维护的斜率，因为我们需要让 $f(v)$ 尽可能小，所以我们维护一个下凸包。
时间复杂度 $O(k(mlogn+nlogn))$
也可以优化到 $O(k(mlogn+n))$ ，由于询问1-n满足单调性，所以不需要二分。

代码

struct line {
    int k, b;
    line() {}
    line(int k, int b) : k(k), b(b) {}
 
    double intersect(line l) {
        //交点
        double db = l.b - b;
        double dk = k - l.k;
        return db / dk;
    }
 
    int operator () (int x) {
        return k * x + b;
    }
    bool operator < (const line x) const {
        return k > x.k;
    }
};
 
struct CHT {
    vector<double> x;
    vector<line> lines;
 
    void init(line l) {
        x.push_back(-INF);
        lines.push_back(l);
    }
 
    void addLine(line l) {
        while (lines.size() >= 2 && l.intersect(lines[lines.size() - 2]) <= x.back()) {
            x.pop_back();
            lines.pop_back();
        }
        x.push_back(l.intersect(lines.back()));
        lines.push_back(l);
    }
 
    int query(int qx) {
        int id = upper_bound(x.begin(), x.end(), qx) - x.begin();
        --id;
        return lines[id](qx);
    }
};
struct node {
    int dis, pos;
    bool operator <(const node &x)const {
        return x.dis < dis;
    }
};
const int MAXN = 1e5 + 5;
struct edge {int v, w;};
vector<edge>g[MAXN];
int dis[MAXN];
bool vis[MAXN];
int n, m, k;
void Dij() {
    for (int i = 1; i <= n; i++)vis[i] = 0;
    priority_queue<node>que;
    for (int i = 1; i <= n; i++)que.push({ dis[i],i });
    while (que.size()) {
        auto x = que.top(); que.pop();
        int u = x.pos, distance = x.dis;
        if (vis[u])continue;
        vis[u] = 1;
        for (edge ed : g[u]) {
            int v = ed.v, w = ed.w;
            if (dis[v] > distance + w) {
                dis[v] = distance + w;
                if (!vis[v])que.push({ dis[v],v });
            }
        }
    }
}
void solve() {
    cin >> n >> m >> k;
    for(int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].pb({v, w});
        g[v].pb({u, w});
    }
    for(int i = 1; i <= n; i++) {
        dis[i] = INF;
    }
    dis[1] = 0;
    Dij();
    while(k--) {
        CHT cht;
        cht.init({0, 0});
        vector<line> lines;
        for(int u = 1; u <= n; u++)
            lines.pb({- 2 * u, dis[u] + u * u});
        sort(lines.begin(), lines.end());
        for(auto l : lines)
            cht.addLine(l);
        for(int v = 1; v <= n; v++)
            dis[v] = cht.query(v) + v * v;
        Dij();
    }
    for(int i = 1; i <= n; i++) {
        cout << dis[i] << ' ';
    }
    cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105