【无标题】斜率优化dp

1.与dp[j]无关

dp[i]=k(j)*f(i)+b[j];

E. Long Way Home

time limit per test

3 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Stanley lives in a country that consists of nn cities (he lives in city 11). There are bidirectional roads between some of the cities, and you know how long it takes to ride through each of them. Additionally, there is a flight between each pair of cities, the flight between cities uu and vv takes (u−v)2(u−v)2 time.

Stanley is quite afraid of flying because of watching "Sully: Miracle on the Hudson" recently, so he can take at most kk flights. Stanley wants to know the minimum time of a journey to each of the nn cities from the city 11.

Input

In the first line of input there are three integers nn, mm, and kk (2≤n≤1052≤n≤105, 1≤m≤1051≤m≤105, 1≤k≤201≤k≤20) — the number of cities, the number of roads, and the maximal number of flights Stanley can take.

The following mm lines describe the roads. Each contains three integers uu, vv, ww (1≤u,v≤n1≤u,v≤n, u≠vu≠v, 1≤w≤1091≤w≤109) — the cities the road connects and the time it takes to ride through. Note that some pairs of cities may be connected by more than one road.

Output

Print nn integers, ii-th of which is

#include 
#include 
#include 
#include 
 
using namespace std;
 
#define int long long
 
const int inf = 1e18;
const int inf1 = 1e15;
 
struct CHT {
    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;
        }
 
        long long operator () (long long x) {
            return k * x + b;
        }
    };
 
    vector<double> x;
    vector ll;
 
    void init(line l) {
        x.push_back(-inf);
        ll.push_back(l);
    }
 
    void addLine(line l) {
        while (ll.size() >= 2 && l.intersect(ll[ll.size() - 2]) <= x.back()) {
            x.pop_back();
            ll.pop_back();
        }
        if (!ll.empty()) {
            x.push_back(l.intersect(ll.back()));
        }
        ll.push_back(l);
    }
 
    long long query(long long qx) {
        int id = upper_bound(x.begin(), x.end(), qx) - x.begin();
        --id;
        return ll[id](qx);
    }
};
 
void dijkstra(vectorint, int>>> &g, vector<int> &dist) {
    const int n = g.size();
    vector<bool> used(n, false);
    priority_queueint, int>> q;
    for (int i = 0; i < n; ++i) {
        q.push({ -dist[i], i });
    }
    while (!q.empty()) {
        int v = q.top().second;
        q.pop();
        if (used[v]) {
            continue;
        }
        used[v] = true;
        for (auto [u, w] : g[v]) {
            if (dist[u] > dist[v] + w) {
                dist[u] = dist[v] + w;
                q.push({ -dist[u], u });
            }
        }
    }
}
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    vectorint, int>>> g(n);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        --u; --v;
        g[u].push_back({ v, w });
        g[v].push_back({ u, w });
    }
    vector<int> dist(n, inf1);
    dist[0] = 0;
    dijkstra(g, dist);
    for (int i = 0; i < k; ++i) {
        CHT cht;
        cht.init(CHT::line(0, 0));
        for (int i = 1; i < n; ++i) {
            cht.addLine(CHT::line(-i * 2, dist[i] + i * i));
        }
        for (int i = 0; i < n; ++i) {
            dist[i] = cht.query(i) + i * i;
        }
        dijkstra(g, dist);
    }
    for (int i : dist) {
        cout << i << ' ';
    }
}

equal to the minimum time of traveling to city ii.