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

There are N cities in the country, and M directional roads from u to v(1≤u,v≤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≤T≤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≤100000,M≤200000,K≤10,0≤C_i≤1e9. There is at least one path between City 1 and City N.

Output
For each test case, print the minimum distance.

样例输入
1
5 6 1
1 2 2
1 3 4
2 4 3
3 4 1
3 5 6
4 5 2

样例输出
3

题意

给你一个图，问你从1到N最多让K条边为0的最短路

题解

d[i][j]代表到j点已经删去i条边的最小值

跑一遍dij

代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define ll long long
 5 const int maxn=1e5+5,maxm=2e5+5;
 6 ll d[11][maxn];
 7 int n,m,k;
 8 int head[maxn],cnt;
 9 struct edge
10 {
11     int v,next;
12     ll w;
13 }edges[maxm];
14 struct node
15 {
16     ll w;
17     int v,k;
18     bool operator<(const node &D)const{
19         return w>D.w;
20     }
21 };
22 void dij()
23 {
24     memset(d,0x3f,sizeof d);
25     priority_queue<node>q;
26     q.push({0,1,0});
27     d[0][1]=0;
28     while(!q.empty())
29     {
30         auto u=q.top();q.pop();
31         if(u.v==n)return;
32         for(int i=head[u.v];i!=-1;i=edges[i].next)
33         {
34             edge &v=edges[i];
35             if(u.k<k&&d[u.k+1][v.v]>d[u.k][u.v])
36                 q.push({d[u.k+1][v.v]=d[u.k][u.v],v.v,u.k+1});
37             if(d[u.k][v.v]>d[u.k][u.v]+v.w)
38                 q.push({d[u.k][v.v]=d[u.k][u.v]+v.w,v.v,u.k});
39         }
40     }
41 }
42 int main()
43 {
44     int t;
45     scanf("%d",&t);
46     while(t--)
47     {
48         memset(head,-1,sizeof head);
49         cnt=0;
50         scanf("%d%d%d",&n,&m,&k);
51         for(int i=0,u,v,w;i<m;i++)
52         {
53             scanf("%d%d%d",&u,&v,&w);
54             edges[cnt].v=v;
55             edges[cnt].w=1LL*w;
56             edges[cnt].next=head[u];
57             head[u]=cnt++;
58         }
59         dij();
60         ll minn=0x3f3f3f3f3f3f3f3f;
61         for(int i=0;i<=k;i++)
62             minn=min(minn,d[i][n]);
63         printf("%lld
",minn);
64     }
65     return 0;
66 }