题目描述

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

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

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

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

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

思路

二分最小费用，然后每次都跑一遍spfa，看血量能否到达终点

#include 
#include 
#include 
#define maxn 100030
#define INF 0x7f7f7f7f
using namespace std;
int l=0,s;
struct arr 
{ 
    int x,y,w,next;   
};
int x,y,z,b,n;
arr edge[maxn];
int ls[maxn];
int a[maxn];
int state[maxn];
bool exits[maxn];
bool spfa(int l)
{
    if (l t;
    t.push(1);
    state[1]=0;
    exits[1]=true;
    while (!t.empty())
    {
        int tt=t.front();
        t.pop();
        i=ls[tt];
        exits[tt]=false;
        while (i!=0) 
        {
            if (a[edge[i].y]<=l&&edge[i].w+state[tt]a[i]) l=a[i];
    }
    for (int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        edge[++t]=(arr){x,y,z,ls[x]};
        ls[x]=t;
        edge[++t]=(arr){y,x,z,ls[y]};
        ls[y]=t;
    }
    int ans=0;
    while (l<=r)
    {
        int m=(l+r)/2;
        if (spfa(m)) 
        {
            ans=m;
            r=m-1;
        }
        else l=m+1;
    }
    if (ans>0) printf("%d",ans);
    else printf("AFK");
    return 0;
}