Luogu P1462 通往奥格瑞玛的道路【二分/最短路】

题目背景

在艾泽拉斯大陆上有一位名叫歪嘴哦的神奇术士，他是部落的中坚力量

有一天他醒来后发现自己居然到了联盟的主城暴风城

在被众多联盟的士兵攻击后，他决定逃回自己的家乡奥格瑞玛

题目描述

在艾泽拉斯，有n个城市。编号为1,2,3,...,n。

城市之间有m条双向的公路，连接着两个城市，从某个城市到另一个城市，会遭到联盟的攻击，进而损失一定的血量。

每次经过一个城市，都会被收取一定的过路费（包括起点和终点）。路上并没有收费站。

假设1为暴风城，n为奥格瑞玛，而他的血量最多为b，出发时他的血量是满的。

歪嘴哦不希望花很多钱，他想知道，在可以到达奥格瑞玛的情况下，他所经过的所有城市中最多的一次收取的费用的最小值是多少。

输入输出格式

输入格式：

第一行3个正整数，n，m，b。分别表示有n个城市，m条公路，歪嘴哦的血量为b。

接下来有n行，每行1个正整数，fi。表示经过城市i，需要交费fi元。

再接下来有m行，每行3个正整数，ai，bi，ci(1<=ai，bi<=n)。表示城市ai和城市bi之间有一条公路，如果从城市ai到城市bi，或者从城市bi到城市ai，会损失ci的血量。

输出格式：

仅一个整数，表示歪嘴哦交费最多的一次的最小值。

如果他无法到达奥格瑞玛，输出AFK。

6月离开机房准备期末考试的最后一道题。

一个月之后才来写题解QAQ。

题目设问为：最多的一次收取的费用的最小值是多少。那么就基本可以确定是二分。

二分？题目设问求费用，那我们二分费用好了。

左边界为l==1，右边界就是全部的点权之和。【这里注意开long long 】! 否则会wa3个点。

void binary()

{

    ll l=,r=sum;

    while(l<r)

    {

        ll mid=(l+r)>>;

        if(spfa_check(mid)) r=mid;

        else l=mid+;

    }

    ans=l;

}

最短路？我们求最短路的目的是看血量是否满足要求。在这里起点和终点都是确定的。

在基本的最短路（这里用的是spfa）上加一个条件：走到的这个点的点权是否满足小于我们二分出的花费。

跑完一遍，如果dis[n]小于血量，则可行，可继续二分。

        for(int i=head[x];i;i=edge[i].next)

        {

            int y=edge[i].to;

            if(dis[y]>dis[x]+edge[i].val&&f[y]<=cnt)

            {

                dis[y]=dis[x]+edge[i].val;

                if(visit[y]==)

                {

                    visit[y]=;

                    q.push(y);

                }

            }

        }

跑最短路的时候记得每次都要初始化一下。

无解判定？我们可以在最开始让花的费用等于inf，进行一遍spfacheck，在如此宽松的条件下都不可行，那必是无解了！输出AFK。

code

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 int inf=0x3f3f3f3f;

 int n,m,b,tot,f[],u[],head[],dis[];

 bool visit[];

 ll ans,sum;

 struct node{

     int to,next,val;

 }edge[];

 void add(int x,int y,int z)

 {

     edge[++tot].to=y;

     edge[tot].val=z;

     edge[tot].next=head[x];

     head[x]=tot;

 }

 bool spfa_check(ll cnt)

 {

     memset(visit,,sizeof(visit));

     queue<int>q;

     for(int i=;i<=n;i++) dis[i]=inf;

     dis[]=;

     visit[]=;

     q.push();

     while(!q.empty())

     {

         int x=q.front();

         q.pop();visit[x]=;

         for(int i=head[x];i;i=edge[i].next)

         {

             int y=edge[i].to;

             if(dis[y]>dis[x]+edge[i].val&&f[y]<=cnt)

             {

                 dis[y]=dis[x]+edge[i].val;

                 if(visit[y]==)

                 {

                     visit[y]=;

                     q.push(y);

                 }

             }

         }

     }

     if(dis[n]<b) return true;

     else return false;

 }

 void binary()

 {

     ll l=,r=sum;

     while(l<r)

     {

         ll mid=(l+r)>>;

         if(spfa_check(mid)) r=mid;

         else l=mid+;

     }

     ans=l;

 }

 int main()

 {

     scanf("%d%d%d",&n,&m,&b);

     for(int i=;i<=n;i++)

         scanf("%d",&f[i]),sum+=f[i];

     for(int i=;i<=m;i++)

     {

         int x=,y=,z=;

         scanf("%d%d%d",&x,&y,&z);

         if(x==y) continue;

         add(x,y,z);

         add(y,x,z);

     }

     if(!spfa_check(inf))

     {

         printf("AFK\n");

         return ;

     }

     binary();

     printf("%lld",ans);

     return ;

 }

巴特西

Luogu P1462 通往奥格瑞玛的道路【二分/最短路】

题目背景

题目描述

输入输出格式

最新文章

热门文章