（警钟敲烂）如果你被一些莫名其妙的错误卡住

P1462 通往奥格瑞玛的道路

lvclengai @ 2023-08-10 22:49:38

蒟蒻调了这个题调了好久（看一下我的提交记录就知道了），总结一下这个题的坑点

1.inf一定要开的非常大，我开到了1e30才过

2.无向图，maxn要开到500005，不然你会莫名其妙RE

十年OI一场空，不开longlong见祖宗

一定，一定，一定要开longlong啊！！！！我是懒狗，直接#define int long long（ps，用了这个你的主函数必须写成signed main()）

4.当血量为0时，还是能到达终点的

5.如果你只 WA#13，那么是你的边界判断出了问题，切记在二分时要保证mid!=f[1]（就是这个点，卡了我一个小时！）

by 棕名 @ 2023-08-10 23:00:20

long long 开 1e30

by OcTar @ 2023-08-10 23:05:23

我 inf 开 0x3f3f3f3f3f3f3f3f 就过了

by lvclengai @ 2023-08-10 23:53:35

@棕名我的代码，反正过了就行doge

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=500005,inf=1e30;
int n,m,b,cnt,l,r;
int cost[maxn];
int dis[maxn],h[maxn],to[maxn],val[maxn],nxt[maxn];
bool vis[maxn];
void add(int a,int b,int c)
{
    to[++cnt]=b;
    val[cnt]=c;
    nxt[cnt]=h[a];
    h[a]=cnt;
}
struct node
{
    int v,w;
    friend bool operator<(node a,node b)
    {
        return a.w>b.w;
    }
}tmp;
priority_queue<node>q;
bool dijkstra(int mid)
{
    while(!q.empty()) q.pop();
    int s=1;
    for(int i=1;i<=n;i++)
    {
        dis[i]=inf;
        vis[i]=0;
    }
    dis[s]=0;
    tmp.v=s,tmp.w=0;q.push(tmp);
    if (cost[1] > mid) return 0;
    while(!q.empty())
    {
        int u=q.top().v;
        q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int i=h[u];i;i=nxt[i])
        {
            if(cost[to[i]]>mid)continue;
            if(dis[to[i]]>dis[u]+val[i])
            {
                dis[to[i]]=dis[u]+val[i];
                tmp.w=dis[to[i]],tmp.v=to[i];q.push(tmp);
            }
        }
    }
    if(dis[n]>b)return 0;
    else return 1;
}
signed main()
{
    cin>>n>>m>>b;
    for(int i=1;i<=n;i++)
    {
        cin>>cost[i];
        r=max(r,cost[i]);
        l=min(l,cost[i]);
    } 
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    int flag=r;

    while(l<r)
    {
        int mid=(l+r)>>1;
        if(dijkstra(mid))
        {
            r=mid;
        }
        else
        {
            l=mid+1;
        }
    }
    if(!dijkstra(l))cout<<"AFK";
    else cout<<l;
    return 0;
}