本文共 1520 字，大约阅读时间需要 5 分钟。
题目连接：
题意：有n个节点p条无向边，现在可以选择其中的任意K条免费，则花费为除了k条边后权值最大的一个，求最小花费多少。
分析：二分枚举最大边长limit，如果图中的边大于limit,则将图中的边当作1，表示免费使用一次，否则就当作0，这样只需判断dist[n]与k的大小，然后继续二分边长就可了。
#include #include #include #include #include #include #include #include #include #include #include #include #define LL long long#define mod 100000000#define inf 0x3f3f3f3f#define eps 1e-9#define N 1000010#define FILL(a,b) (memset(a,b,sizeof(a)))#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define PII pair using namespace std;struct edge{ int to,w; edge(){} edge(int to,int w):to(to),w(w){} bool operator<(const edge &a)const{ return w>a.w; }};vector g[N];int n,m,k;int dis[N],vis[N];int ok(int limit){ for(int i=1;i<=n;i++)dis[i]=inf,vis[i]=0; priority_queue que; dis[1]=0; que.push(edge(1,0)); while(!que.empty()) { edge now=que.top();que.pop(); int x=now.to; if(vis[x])continue; vis[x]=1; for(int i=0,sz=g[x].size();i limit?1:0; if(dis[v]>dis[x]+w) { dis[v]=dis[x]+w; que.push(edge(v,dis[v])); } } } return dis[n]<=k;}int solve(){ int l=0,r=N,ans=-1; while(l<=r) { int mid=(l+r)>>1; if(ok(mid))r=mid-1,ans=mid; else l=mid+1; } return ans;}int main(){ while(scanf("%d%d%d",&n,&m,&k)>0) { for(int i=1;i<=n;i++)g[i].clear(); for(int i=1;i<=m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); g[u].push_back(edge(v,w)); g[v].push_back(edge(u,w)); } printf("%d\n",solve()); }}
转载于:https://www.cnblogs.com/lienus/p/4274707.html
