LibreOJ10075. 「一本通 3.2 练习 1」农场派对【二分+最短路】

10075. 「一本通 3.2 练习 1」农场派对

【题目描述】

传送门

【题解】

我们知道当前的边权肯定不是题目中给的,我们需要换一种思路,二分这个答案t,权值大于t的边权给1,否则给0,跑最短路。
最后我们要dst[n]<=K的情况。

代码如下

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1005,MAXM=2005;
int n,m,K,tl,hd,Ans=-1,que[MAXM*3],dst[MAXN];
bool vis[MAXN];
struct Edge{
    int tot,lnk[MAXN],nxt[MAXM<<1],son[MAXM<<1],W[MAXM<<1];
    void Add(int x,int y,int w){nxt[++tot]=lnk[x],lnk[x]=tot;son[tot]=y,W[tot]=w;}
}E;
bool SPFA(int t){
    memset(dst,63,sizeof(dst));
    hd=0,vis[que[tl=1]=1]=1;dst[1]=0;
    while(hd^tl){
        int x=que[++hd];vis[x]=0;
        for(int j=E.lnk[x];j;j=E.nxt[j])
        if(dst[E.son[j]]>dst[x]+(E.W[j]>t)){
            dst[E.son[j]]=dst[x]+(E.W[j]>t);
            if(!vis[E.son[j]]) vis[que[++tl]=E.son[j]]=1;
        }
    }
    return dst[n]<=K;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("prob.in","r",stdin);
    freopen("prob.out","w",stdout);
    #endif
    scanf("%d%d%d",&n,&m,&K);
    for(int i=1,x,y,w;i<=m;i++) scanf("%d%d%d",&x,&y,&w),E.Add(x,y,w),E.Add(y,x,w);
    for(int L=0,R=1e9,mid=(R+L)>>1;L<=R;mid=(R+L)>>1) if(SPFA(mid)) Ans=mid,R=mid-1;else L=mid+1;
    printf("%d\n",Ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部