样例解释
二分 + 最短路模型
进一步解释:题目要求我们最多把k条边置为0,使得1到N号的剩余路线中,最大的花费最小
那么我们可以假设一个解为x,只要$egde_i \leq x$的边都置为0。$egde_i \geq x$都置为1,这样我们只关注那些等于1的边,从1到N等于1的边个数小于等于k(即要去掉边的个数$\leq k$),那么这个解就是成立的!
因此这个题是可以使用二分来做的, 图示如下
到了这里,下面就是求解从1到N边权为1最少条数的路径,发现这就完美转化为了一个最短路问题。因为只有边权为0和1的边,写一个不会TLE的解法就可。还是y总的代码写得漂亮就抄y总的吧🤐
注意二分的起始区间是$[0,1 + max(L_1, L_2, .... L_m)]$, 当最终解是$1 + max(L_1, L_2, .... L_m)$时,表示方案无解(因为农夫的花费怎么也不可能比最大的边还要大嘛)
代码
用朴素版的dijkstra能过
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e3 + 10, INF = 0x3f3f3f3f;
int n, m, k;
int g[N][N];
int dist[N];
bool st[N];
int dijkstra(int x)
{
memset(st, 0, sizeof st);
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for(int i = 0; i < n - 1; i++)
{
int u = -1;
for(int j = 1; j <= n; j++)
{
if(!st[j] && (u == -1 || dist[j] < dist[u])) u = j;
}
if(st[n]) break;
st[u] = true;
for(int j = 1; j <= n; j++)
{
if(g[u][j] == INF) continue;
int d = g[u][j] > x;
dist[j] = min(dist[j], dist[u] + d);
}
}
return dist[n];
}
int main()
{
cin >> n >> m >> k;
memset(g, 0x3f, sizeof g);
int maxv = -INF;
for(int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
g[a][b] = g[b][a] = min(c, g[a][b]);
maxv = max(maxv, c);
}
int l = 0, r = maxv + 1;
while(l < r)
{
int mid = l + r >> 1;
if(dijkstra(mid) <= k) r = mid;
else l = mid + 1;
}
if(l == maxv + 1) l = -1;
cout << l << endl;
return 0;
}
我只能看懂你的样例解释,没看懂你在写什么
没有注释真的难懂