luogu题解 P1462 【通往奥格瑞玛的道路】二分+spfa
阅读原文时间:2023年07月16日阅读:3
  • 题目链接:

    https://www.luogu.org/problemnew/show/P1462

  • 思路:

    又是一道水题,很明显二分+最短路

    而且这道题数据非常水,spfa有个小错误居然拿了91分还比正解快

    我们二分金钱数,节点权值大于二分值的都不能走。二分中跑spfa,如果不能走到终点,即dis[n]>=b,则说明二分值偏小。

  • 注意:

  • 代码:

    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #define ri register int
    #define ll long long
    using namespace std;
    const ll inf=9926081792;
    const int maxn=10005;
    const int maxm=50005;
    ll g[maxn],dis[maxn];
    int h[maxn],num_edge=0;
    bool vis[maxn];
    int n,m;
    ll b;
    struct Edge{
    int ne,to;
    ll dis;
    }edge[maxm<<2]; inline void add_edge(int f,int t,ll dis){ edge[++num_edge].ne=h[f]; edge[num_edge].to=t; edge[num_edge].dis=dis; h[f]=num_edge; } template inline void read(T &x){
    x=0;int ne=0;char c;
    while(!isdigit(c=getchar()))ne=c=='-';
    x=c-48;
    while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48; x=ne?-x:x; return ; } inline int spfa(ll len){ dequeq;
    int u,v,c;
    while(q.size())q.pop_front();
    //memset(vis,0,sizeof(vis));
    for(ri i=1;i<=n;i++){dis[i]=inf,vis[i]=0;} dis[1]=0,vis[1]=1; q.push_back(1); while(!q.empty()){ u=q.front();q.pop_front(); for(ri i=h[u];i;i=edge[i].ne){ v=edge[i].to; if((len-g[v]>=0)&&dis[v]>dis[u]+edge[i].dis){
    dis[v]=dis[u]+edge[i].dis;
    if(q.empty()){
    if(!vis[v]){
    vis[v]=1;
    q.push_back(v);
    }
    }
    c=q.front();
    if(dis[v]>dis[c]){
    if(!vis[v]){
    vis[v]=1;
    q.push_back(v);
    }
    }
    else if(!vis[v]){
    vis[v]=1;
    q.push_front(v);
    }

            }
        }
        vis[u]=0;
    }
    if(dis[n]>=b)return 0;
    return 1;

    }
    int main(){
    ll l=1,r=n;
    int u,v,c;
    read(n),read(m),read(b);
    for(ri i=1;i<=n;i++)read(g[i]); for(ri i=1;i<=m;i++){ read(u),read(v),read(c); add_edge(u,v,c); add_edge(v,u,c); } if(!spfa(inf)){ puts("AFK"); return 0; } while(l>1;
    if(spfa(mid))r=mid;
    else l=mid+1;
    }
    printf("%d",r);
    return 0;
    }

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章