NEERC17 J Journey from Petersburg to Moscow

CF上可以提交。   链接

依然是很妙的解法。

我们可以枚举每一个出现过的边权$L$，然后把所有边的边权减掉这个$L$，如果小于$L$就变为$0$，然后跑一遍最短路然后加上$k * L$更新答案即可。

注意$L$也可以取到$0$。

这样做就是强制让出了前$k$大的边的边权，所以能计算到所有答案。

时间复杂度$O(n^2logn)$。

Code：

#include <cstdio>

#include <cstring>

#include <queue>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long ll;

typedef pair <ll, int> pin;

const int N = ;

const ll inf = 0x3f3f3f3f3f3f3f3f;

int n, m, K, vCnt = , tot = , head[N];

ll eVal[N], dis[N];

bool vis[N];

struct Edge {

    int to, nxt;

    ll val;

} e[N << ];

inline void add(int from, int to, ll val) {

    e[++tot].to = to;

    e[tot].val = val;

    e[tot].nxt = head[from];

    head[from] = tot;

}

template <typename T>

inline void read(T &X) {

    X = ; char ch = ; T op = ;

    for(; ch > '' || ch < ''; ch = getchar())

        if(ch == '-') op = -;

    for(; ch >= '' && ch <= ''; ch = getchar())

        X = (X << ) + (X << ) + ch - ;

    X *= op;

}

inline ll max(ll x, ll y) {

    return x > y ? x : y;

}

template <typename T>

inline void chkMin(T &x, T y) {

    if(y < x) x = y;

}

priority_queue <pin> Q;

void dij(ll nowL) {

    memset(dis, 0x3f, sizeof(dis));

    memset(vis, , sizeof(vis));

    Q.push(pin(dis[] = 0LL, ));

    for(; !Q.empty(); ) {

        int x = Q.top().second; Q.pop();

        if(vis[x]) continue;

        vis[x] = ;

        for(int i = head[x]; i; i = e[i].nxt) {

            int y = e[i].to; ll val = max(0LL, e[i].val - nowL) + dis[x];

            if(val < dis[y]) {

                dis[y] = val;

                Q.push(pin(-dis[y], y));

            }

        }

    }

}

int main() {

    read(n), read(m), read(K);

    for(int i = ; i <= m; i++) {

        int x, y; ll v;

        read(x), read(y), read(v);

        add(x, y, v), add(y, x, v);

        eVal[++vCnt] = v;

    }

    eVal[++vCnt] = 0LL;

    sort(eVal + , eVal +  + vCnt);

    vCnt = unique(eVal + , eVal +  + vCnt) - eVal - ;

    ll ans = inf;

    for(int i = ; i <= vCnt; i++) {

        dij(eVal[i]);

        chkMin(ans, dis[n] + 1LL * K * eVal[i]);

    }

    printf("%lld\n", ans);

    return ;

}