Magical Girl Haze 计蒜客-A1958（分层最短路）

题意：

给一张有向图，可以把$k$条边的边权变成$0$，求点$1$到$n$的最短路。

思路：

$dp$+$dijkstra$思想。

$dis[i][k]$表示点$1$到$i$实行了$k$次把边权变为$0$的操作之后的最短距离。转移为：

$dis[v][k]=min(dis[v][k],dis[u][k]+w)$

$dis[v][k+1]=min(dis[v][k+1],dis[u][k])$

代码：

  1 //#include<bits/stdc++.h>
  2 #include <set>
  3 #include <map>
  4 #include <stack>
  5 #include <cmath>
  6 #include <queue>
  7 #include <cstdio>
  8 #include <string>
  9 #include <vector>
 10 #include <cstring>
 11 #include <iostream>
 12 #include <algorithm>
 13 
 14 #define ll long long
 15 #define pll pair<ll,ll>
 16 #define pii pair<int,int>
 17 #define bug printf("*********
")
 18 #define FIN freopen("input.txt","r",stdin);
 19 #define FON freopen("output.txt","w+",stdout);
 20 #define IO ios::sync_with_stdio(false),cin.tie(0)
 21 #define ls root<<1
 22 #define rs root<<1|1
 23 #define pb push_back
 24 
 25 using namespace std;
 26 const int inf = 2e9 + 7;
 27 const ll Inf = 1e18 + 7;
 28 const int maxn = 2e5 + 5;
 29 const int mod = 1e9 + 7;
 30 
 31 struct node
 32 {
 33     int v, w, next;
 34 }edge[maxn<<1];
 35 
 36 struct qnode
 37 {
 38     int u, k;
 39     ll dis;
 40     qnode(int u,int k,ll dis):u(u),k(k),dis(dis){}
 41     bool operator <(const qnode& a)const {
 42         return dis > a.dis;
 43     }
 44 };
 45 
 46 int head[maxn], tot = 0;
 47 ll dis[maxn][20];
 48 int n, m, k;
 49 
 50 void init()
 51 {
 52     tot = 0;
 53     memset(head, -1, sizeof head);
 54 }
 55 
 56 void add(int u, int v, int w)
 57 {
 58     edge[tot].v = v, edge[tot].w = w;
 59     edge[tot].next = head[u];
 60     head[u] = tot++;
 61 }
 62 
 63 ll dij()
 64 {
 65     priority_queue<qnode>q;
 66     
 67     for (int i = 1; i <= n; ++i)
 68         for (int j = 0; j <= k; ++j)    dis[i][j] = Inf;
 69 
 70     dis[1][0] = 0;
 71     q.push(qnode(1, 0, 0));
 72     while (!q.empty())
 73     {
 74         int u = q.top().u, kk = q.top().k;
 75         if (u == n)    return dis[u][kk];//已经全部更新结束
 76         q.pop();
 77         for (int i = head[u]; i != -1; i = edge[i].next)
 78         {
 79             int v = edge[i].v, w = edge[i].w;
 80             if (dis[u][kk] + w < dis[v][kk])//保留这条边
 81             {
 82                 dis[v][kk] = dis[u][kk] + w;
 83                 q.push(qnode(v, kk, dis[v][kk]));
 84             }
 85             if (kk != k)//去除这条边
 86             {
 87                 if (dis[v][kk + 1] > dis[u][kk])
 88                 {
 89                     dis[v][kk + 1] = dis[u][kk];
 90                     q.push(qnode(v, kk + 1, dis[v][kk + 1]));
 91                 }
 92             }
 93         }
 94     }
 95     return -1;
 96 }
 97 
 98 int main()
 99 {
100     int T;
101     scanf("%d", &T);
102     while (T--)
103     {
104         init();
105         scanf("%d %d %d", &n, &m, &k);
106         while (m--)
107         {
108             int u, v, w;
109             scanf("%d %d %d", &u, &v, &w);
110             add(u, v, w);
111         }
112         printf("%d
", dij());
113     }
114 }