https://ac.nowcoder.com/acm/contest/884/J

卡了2个小时的题 其实也不是很难 大家都做出来了 我们好菜
题意 给一个无向图 给出S T两个点 要从S走到T 最多删去K条边 问最短的权值之和

具体想法看代码吧 用迪杰斯特拉跑最短路 里面改一点 我又是抄的咖啡鸡的神仙代码 真的写的太美了

#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<ctime>
#include<map>
#include<stack>
#include<set>
#include<cstring>
#include<sstream>
#include<queue>

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
const int maxn = 1e3 + 5;
int n, m, S, T, k, dis[maxn][maxn];//dis是从s到i点免费j条边的权值
vector<pi> h[maxn];//边

struct node {
	int u, s, dis;//u是dis[i] s是i
	bool operator<(const node& u) const {
		return dis > u.dis;
	}
};

priority_queue<node> q;//优先队列q 优化时间复杂度

int main() {
	cin >> n >> m >> S >> T >> k;
	while (m--) {
		int u, v, w;
		cin >> u >> v >> w;
		h[u].push_back(pi{ v, w });//建图
		h[v].push_back(pi{ u, w });//建图
	}
	memset(dis, -1, sizeof(dis));//初始化为1
	dis[S][0] = 0;//初始化起始点
	q.push(node{ S,0,0 });//入队
	while (!q.empty()) {
		node tmp = q.top();//取出权值最小的
		q.pop();
		int u = tmp.u;//起始点
		int s = tmp.s;//已经免费的边数
		for (auto e : h[u]) {//遍历该起始点所有连到边
			int v = e.first;//该边的终点
			if (dis[v][s] == -1 || dis[v][s] >= dis[u][s] + e.second) {//起始点到v点没有线或者起始点到v的距离大于起始点到u点再到v点的距离 松弛操作
				dis[v][s] = dis[u][s] + e.second;//更新
				q.push(node{ v,s,dis[v][s] });//入队列
			}
			if (s == k) continue;//如果免费的边数用完了
			if (dis[v][s + 1] == -1 || dis[v][s + 1] > dis[u][s]) {//起始点到v 大于起始点到u 直接省略了v和s之间的那段距离
				dis[v][s + 1] = dis[u][s];//处理免费边部分
				q.push(node{ v,s + 1,dis[v][s + 1] });
			}
		}
	}
	int ans = 1e9;
	for (int i = 0; i <= k; i++) {//遍历 S -> T 之间省几条边最便宜
		if (dis[T][i] != -1) {
			ans = min(ans, dis[T][i]);
		}
	}
	cout << ans << endl;
	return 0;
}