各种神作不解释QAQQQ
先是写了个作死的spfa本机过了交上去T了。。。
然后不想写Dijkstra各种自暴自弃。。。
最后改了一下步骤加了个SLF过了。。。
首先一个trivial的想法是$dis[p][t]$表示到了$p$号节点，用了$t$次变0技能，然后可以用$dis[q][t] + e[q][p]$和$dis[q][t - 1] + e[q][p] * 0$来更新
然后点数$O(n * k)$，边数$O(m * k)$，再加上usaco硬卡spfa。。。什么最终鬼畜。。。
其实我们可以这样子想：
先把用了$t$次技能的$dis$先算出来，这就是用$dis[q][t] + e[q][p]$更新
然后计算用了$t + 1$次技能，方法就是先用$dis[q]$更新$dis[p]$表示用了一次技能，再跑一边spfa就好了
1 /************************************************************** 2 Problem: 1579 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:4312 ms 7 Memory:3872 kb 8 ****************************************************************/ 9 10 #include11 #include 12 #include 13 14 using namespace std;15 const int N = 1e4 + 5;16 const int M = 5e4 + 5;17 const int K = 25;18 const int inf = 1e9;19 const int Maxlen = M * 3 * 10;20 21 struct edge {22 int next, to, v;23 edge(int _n = 0, int _t = 0, int _v = 0) : next(_n), to(_t), v(_v) {}24 } e[M << 1];25 26 int n, m, k;27 int first[N], tot;28 int dis[N], tmp[N], v[N];29 30 char buf[Maxlen], *c = buf;31 int Len;32 33 inline int read();34 35 inline void Add_Edges(int x, int y, int z) {36 e[++tot] = edge(first[x], y, z), first[x] = tot;37 e[++tot] = edge(first[y], x, z), first[y] = tot;38 }39 40 #define y e[x].to41 void spfa(int S) {42 static int i, x, q[70000], p;43 static unsigned short l, r;44 for (i = 1; i <= n; ++i) dis[i] = i == S ? 0 : inf;45 q[l = r = 0] = S, v[S] = 1;46 for (i = 1; i <= k + 1; ++i) {47 while (l != r + 1) {48 p = q[l++];49 for (x = first[p]; x; x = e[x].next)50 if (dis[p] + e[x].v < dis[y]) {51 dis[y] = dis[p] + e[x].v;52 if (!v[y]) {53 v[y] = 1;54 if (dis[y] < dis[q[l]]) q[--l] = y;55 else q[++r] = y;56 }57 }58 v[p] = 0;59 }60 if (i == k + 1) continue;61 for (p = 1; p <= n; ++p)62 for (tmp[p] = inf, x = first[p]; x; x = e[x].next)63 tmp[p] = min(tmp[p], dis[y]);64 memcpy(dis, tmp, sizeof(dis));65 for (p = 1; p <= n; ++p)66 if (!v[p]) {67 v[p] = 1;68 if (dis[p] < dis[q[l]]) q[--l] = p;69 else q[++r] = p;70 }71 }72 }73 #undef y74 75 int main() {76 Len = fread(c, 1, Maxlen, stdin);77 buf[Len] = '\0';78 int i, x, y, z;79 n = read(), m = read(), k = read();80 for (i = 1; i <= m; ++i) {81 x = read(), y = read(), z = read();82 Add_Edges(x, y, z);83 }84 spfa(1);85 printf("%d\n", dis[n]);86 return 0;87 }88 89 inline int read() {90 int x = 0;91 while (*c < '0' || '9' < *c) ++c;92 while ('0' <= *c && *c <= '9')93 x = x * 10 + *c - '0', ++c;94 return x;95 }