CF1715E Long Way Home

· · 题解

题意

给定一张 n 个点，m 条边的无向图，边有边权，可以顺着边走产生大小为边权的代价，也可以从 u 点传送到 v 点并产生 (u-v)^2 的代价，至多传送 k 次，求从 1 号点出发到 n 个点中的每一个点的最小代价。

思路

最短路和斜率优化 dp。

考虑设计状态，f[i][u] 表示已经传送了 i 次，此时在 u 号点的最小代价。

显然当 i=0 时，直接跑一遍最短路就可以了。

考虑如何转移 i-1\to i，先讨论最后一次行动是传送的情况，转移为：

\begin{aligned} f[i][u]=\min_{v}\{f[i-1][v]+(u-v)^2\} \end{aligned}

第一维完全可以不要，优化空间复杂度：

\begin{aligned} f[u]=\min_{v}\{f[v]+(u-v)^2\} \end{aligned}

然后讨论最后一次行动是在边上走的情况，跑一遍最短路即可。

但是这样转移的时间复杂度是 O(n^2) 的，无法接受。

考虑用斜率优化的方式快速求出决策点 v，将原式的 \min 去掉，展开移项得到：

\begin{aligned} f[v]+v^2=2u\times v+f[u]-u^2 \end{aligned}

转化为一次函数 y=kx+b 的形式得到：

\begin{array}{l} y=f[v]+v^2 \\ k=2u \\ x=v \\ b=f[u]-u^2 \end{array} \right.

对应形成的点的坐标就是 (v,f[v]+v^2)，最小化 f[u] 就是最小化截距 b，又因为从 1 到 n，斜率 k 单调递增，我们维护一个下凸包即可。

代码

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1E5 + 10;
int n, m, k;
int f[N], g[N], ans[N];
bool vis[N];

struct Edge
{
    int nxt, to, val;
}G[N * 4];
int head[N], cnt;

void add(int u, int v, int w)
{
    G[++cnt].nxt = head[u];
    G[cnt].to = v;
    G[cnt].val = w;
    head[u] = cnt;
}

void spfa()
{
    queue<int> Q;
    memset(vis, 0, sizeof(vis));
    for(int i = 1; i <= n; i++)
    {
        Q.push(i);
        vis[i] = 1;
    }
    while(!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        vis[u] = 0;
        for(int i = head[u]; i; i = G[i].nxt)
        {
            int v = G[i].to;
            if(f[v] > f[u] + G[i].val)
            {
                f[v] = f[u] + G[i].val;
                if(!vis[v])
                {
                    Q.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
}

int X(int j){return j;}
int Y(int j){return g[j] + j * j;}
double slope(int i, int j){return (X(i) - X(j)) ? (double)(Y(i) - Y(j)) / (double)(X(i) - X(j)) : 2100000000;}

signed main()
{
    memset(ans, 0x3f, sizeof(ans));
    cin >> n >> m >> k;
    for(int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
        add(v, u, w);
    }
    memset(f, 0x3f, sizeof(f));
    f[1] = 0;
    spfa();
    while(k--)
    {
        int Q[N];
        int h = 1, t = 0;
        memset(Q, 0, sizeof(Q));
        memcpy(g, f, sizeof(g));
        for(int i = 1; i <= n; i++)
        {
            while(h < t && slope(Q[t - 1], Q[t]) >= slope(Q[t], i))
                t--;
            Q[++t] = i;
        }
        for(int i = 1; i <= n; i++)
        {
            while(h < t && slope(Q[h], Q[h + 1]) <= (double)i * 2.0)
                h++;
            f[i] = g[Q[h]] + (i - Q[h]) * (i - Q[h]);
        }
        spfa();
        for(int i = 1; i <= n; i++)
            ans[i] = min(ans[i], f[i]);
    }
    for(int i = 1; i <= n; i++)
        cout << ans[i] << " ";
    return 0;
}