传送门:https://nanti.jisuanke.com/t/A1958
题意：n个点m条边的路，你有k次机会将某条路上的边权变为0，问你最短路径长度
题解：最短路变形，我们需要在常规的最短路上多开 一维，记录，我消耗j次机会时的最短路径长度为多少
代码：
/** * ┏┓ ┏┓ * ┏┛┗━━━━━━━┛┗━━━┓ * ┃ ┃ * ┃ ━ ┃ * ┃ ＞ ＜ ┃ * ┃ ┃ * ┃... ⌒ ... ┃ * ┃ ┃ * ┗━┓ ┏━┛ * ┃ ┃ Code is far away from bug with the animal protecting * ┃ ┃ 神兽保佑,代码无bug * ┃ ┃ * ┃ ┃ * ┃ ┃ * ┃ ┃ * ┃ ┗━━━┓ * ┃ ┣┓ * ┃ ┏┛ * ┗┓┓┏━┳┓┏┛ * ┃┫┫ ┃┫┫ * ┗┻┛ ┗┻┛ */ #include <set> #include <map> #include <deque> #include <queue> #include <stack> #include <cmath> #include <ctime> #include <bitset> #include <cstdio> #include <string> #include <vector> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; typedef pair<LL, LL> pLL; typedef pair<LL, int> pLi; typedef pair<int, LL> pil;; typedef pair<int, int> pii; typedef unsigned long long uLL; #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define bug printf("********* ") #define FIN freopen("input.txt","r",stdin); #define FON freopen("output.txt","w+",stdout); #define IO ios::sync_with_stdio(false),cin.tie(0) #define debug1(x) cout<<"["<<#x<<" "<<(x)<<"] " #define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"] " #define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"] " LL read() { int x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-')f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } const double eps = 1e-8; const int mod = 1e9 + 7; const int maxn = 3e5 + 5; const int INF = 0x3f3f3f3f; const LL INFLL = 0x3f3f3f3f3f3f3f3f; struct EDGE { int v, nxt, w; } edge[maxn]; int head[maxn]; int tot; void add_edge(int u, int v, int w) { edge[tot].v = v; edge[tot].w = w; edge[tot].nxt = head[u]; head[u] = tot++; } struct node { int u; LL dis; int cnt; node() {} node(int u1, int dis1, int cnt1) { u = u1, dis = dis1, cnt = cnt1; } bool operator < (const node &a) const { return a.dis < dis; } }; LL dis[maxn][15]; LL vis[maxn][15]; LL dij(int st, int ed, int k) { memset(dis, INF, sizeof(dis)); memset(vis, 0, sizeof(vis)); priority_queue<node> q; dis[st][0] = 0; q.push(node(st, 0, 0)); while(!q.empty()) { node tmp = q.top(); q.pop(); int u = tmp.u; int cnt = tmp.cnt; if(u == ed) { return tmp.dis; } if(vis[u][cnt]) continue; vis[u][cnt] = 1; for(int i = head[u]; i != -1; i = edge[i].nxt) { int v = edge[i].v; if(dis[v][cnt] > dis[u][cnt] + edge[i].w) { dis[v][cnt] = dis[u][cnt] + edge[i].w; q.push(node(v, dis[v][cnt], cnt)); } if (cnt + 1 <= k && !vis[v][cnt + 1] && dis[u][cnt] < dis[v][cnt + 1]) { // 当前边权为0，状态更新 dis[v][cnt + 1] = dis[u][cnt]; q.push(node(v, dis[v][cnt + 1], cnt + 1)); } } } return -1; } int main() { #ifndef ONLINE_JUDGE FIN #endif int T; scanf("%d", &T); while(T--) { int n, m, k; memset(head, -1, sizeof(head)); tot = 0; scanf("%d%d%d", &n, &m, &k); for(int i = 1, u, v, w; i <= m; i++) { scanf("%d%d%d", &u, &v, &w); add_edge(u, v, w); } LL ans = INF; for (int i = 0; i <= k; ++i) // 0 到 k ans = min(ans, dij(1, n, i)); printf("%lld ", ans); } return 0; }