[文章目录]
Description
小h最近准备给家里新装条电话线，好让他在奥运假期能够天天上网冲浪，不用再忍受那昂贵的无线上网。 电信局的工作人员对小h说，电话线网络上有n个站点，它们用m条边来连接，小h家的站点在1号，连接的终点在n号，站点之间有电线连接，而且有一定的费用，然后因为暑期的原因，在1号站点连接到n号站点的线路上有k条线是免费的，然后在这条线路剩下的线中费用最大的为小h连接到n号站要付的费用。 当然，小h希望他要付的钱最少，于是他就出了这道题，希望有人能帮帮他。
（1<n<=1000,1<m<=n*(n-1)/2) 0<=cost<=10000
没错，我这个蒟蒻啊，居然啥都没想出来。WA了36%以为是评测出了问题。
本来的想法是：跑一个最小生成树，将路径上的前k大的边权舍掉。然而，举一个反例，1~n有一条边权老大的边。然后，最小生成树根本用不上这个边。
然而。我。。。死活没想到怎么解决。
正解：%%%CKHdalao
二分答案，然后check，怎么检验？？？
然而。我。。。死活没想到怎么解决。+1
正解：%%%CKHdalao+1
直接spfa，边权小于mid的边就相当于不需要消耗k，边权为0，大于的边权相当于1。1~n的最短路就是1~n的路径中最少的数目的边权大于mid。
嗯，我。。。死活没想到怎么解决。啊啊啊啊！蒟蒻附体啊。。。
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,m,k,mx;
queue<int>q;
int head[1100],to[1001000],nxt[1001000],cnt,data[1001000];
void add(int x,int y,int z)
{
to[++cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
data[cnt]=z;
}
int dis[1100];
bool v[1100];
bool check(int x)
{
memset(dis,0x3f,sizeof(dis));
memset(v,0,sizeof(v));
while(!q.empty()) q.pop();
q.push(1);v[1]=1;dis[1]=0;
int y;
while(!q.empty())
{
y=q.front();q.pop();v[y]=0;
for(int i=head[y];i;i=nxt[i])
if(dis[y]+(data[i]>x)<dis[to[i]])
{
dis[to[i]]=dis[y]+(data[i]>x);
if(!v[to[i]]) q.push(to[i]),v[to[i]]=1;
}
}
return dis[n]<=k;
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int x,y,z,i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
mx=max(mx,z);
add(x,y,z);add(y,x,z);
}
int l=0,r=mx+1,mid;
while(l<r)
{
mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
printf("%d",r);
return 0;
}算法对了之后1A。码力好像提升了