计蒜客 ACM-ICPC 2018 南京赛区网络预赛 L. Magical Girl Haze

  • 2018-09-04
  • 12
  • 0

Description:

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

Input:

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

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

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

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

0 \le C_i \le 1e9. There is at least one path between City 1 and City 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代码:

评论

还没有任何评论,你来说两句吧