[牛客暑期多校第四场][最短路变形]J-free

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

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

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

#include
#include
#include
#include
#include
#include
#include
#include
#include

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 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 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;
}