计蒜客 ACM-ICPC 2018 南京赛区网络预赛 L. Magical Girl Haze(分层图最短路)

Description:

There are $N$N cities in the country, and $M$M directional roads from $u$u to $v(1\le u,v\le n)$v(1≤u,v≤n). Every road has a distance $c_i$ci​. Haze is a Magical Girl that lives in City $1$1, she can choose no more than $K$K roads and make their distances become $0$0. Now she wants to go to City $N$N, please help her calculate the minimum distance.

Input:

The first line has one integer $T(1\le T\le 5)$T(1≤T≤5), then following $T$T cases.

For each test case, the first line has three integers $N,M$N,M and $K$K.

Then the following $M$M lines each line has three integers, describe a road, $U_i,V_i,C_i$Ui​,Vi​,Ci​. There might be multiple edges between $u$u and $v$v.

It is guaranteed that $N\le 100000,M\le 200000,K\le 10$N≤100000,M≤200000,K≤10,

$0\le C_i\le 1e9$0≤Ci​≤1e9. There is at least one path between City $1$1 and City $N$N.

Output

For each test case, print the minimum distance.

Sample Input:

1
5 6 1
1 2 2
1 3 4
2 4 3
3 4 1
3 5 6
4 5 2

Sample Output:

3

题目链接

题目是要求最多使K条边长度变为0之后由点1到点N的最短路。

看了学长博客之后才看懂这道题的分层图做法

ACM-ICPC 2018 南京赛区网络预赛 L. Magical Girl Haze (分层图)

建立K+1层图，之后对每层图内每条边建立一条由此层指向上一层的权值为0的边，跑所有图的最短路。

最后找到N点在K+1个图层最短路的最小值即为结果。

例若K=1则在前两层找N点最短路的最小值，第0层代表没有将任何边的权值改变为0，第1层代表将一条边的权值改变为0（因为在最短路的贪心中在某条跨层边（此边即为权值改变为0的边）中由第0层上升到第1层之后仅仅在第 1层中跑最短路，不会再出现跨层（单向边））。

AC代码:

#include <bits/stdc++.h>

const int maxn = 1e5 + 5;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;

struct Link {
    long long V, Weight, Next;
    Link(long long _V = 0, long long _Weight = 0, long long _Next = 0): V(_V), Weight(_Weight), Next(_Next) {}
};

Link edges[(maxn << 2) * 12];
int Head[maxn * 12];
int Tot;
long long Dis[maxn * 12];

void Init() {
    Tot = 0;
    memset(Head, -1, sizeof(Head));
}

void AddEdge(long long U, long long V, long long Weight) {
    edges[Tot] = Link (V, Weight, Head[U]);
    Head[U] = Tot++;
}

struct Cmp {
    bool operator() (const int &A, const int &B) {
        return Dis[A] > Dis[B];
    }
};

int T;
int N, M, K;
long long Ans;

void Dijkstra(int Start) {
    std::priority_queue<int, std::vector<int>, Cmp> Que;
    memset(Dis, INF, sizeof(Dis));
    Dis[Start] = 0;
    Que.push(Start);
    while (!Que.empty()) {
        int U = Que.top(); Que.pop();
        for (int i = Head[U]; i != -1; i = edges[i].Next) {
            Link &Temp = edges[i];
            if (Dis[Temp.V] > Dis[U] + Temp.Weight) {
                Dis[Temp.V] = Dis[U] + Temp.Weight;
                Que.push(Temp.V);
            }
        }
    }
}

int main(int argc, char *argv[]) {
    scanf("%d", &T);
    for (int Case = 1; Case <= T; ++Case) {
        Init();
        scanf("%d%d%d", &N, &M, &K);
        for (long long i = 0, U, V, C; i < M; ++i) {
            scanf("%lld%lld%lld", &U, &V, &C);
            for (int j = 0; j <= K; ++j) {
                AddEdge(U + j * N, V + j * N, C);
                if (j != K) {
                    AddEdge(U + j * N, V + (j + 1) * N, 0);
                }
            }
        }
        Dijkstra(1);
        Ans = INF;
        for (int i = 0; i <= K; ++i) {
            Ans = std::min(Ans, Dis[N + i * N]);
        }
        printf("%lld\n", Ans);
    }
    return 0;
}