Dijkstra 50pts WA求助

P1462 通往奥格瑞玛的道路

LeNotFound @ 2023-01-09 01:02:17

RT 二楼贴代码

思路：Dijkstra跑最短路，每次松弛记录前驱，然后检查 dis[n] 是否为负，如果负数输出AFK，否则通过记录的前驱推出路径，然后遍历路径上的点权找最大值。

by LeNotFound @ 2023-01-09 01:02:36

#include<bits/extc++.h>

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

inline long long read()
{
    long long x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')
        {
            f=-1;
        }
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const ll inf=LONG_LONG_MAX;

vector<ll> dq;

vector<ll> pre;

struct node
{
    ll v,w;
    friend bool operator<(node x, node y)
    {
        return x.w>y.w;
    }
}tmp;

vector<vector<node>> G;

__gnu_pbds::priority_queue<node> q;

ll n,m;

ll b;

void Dijksrta()
{
    vector<ll> dis(n+1,inf);
    vector<bool> vis(n+1,false);

    dis[1]=0;
    tmp.w=0;
    tmp.v=1;

    q.push(tmp);

    while(!q.empty())
    {
        ll u=q.top().v;
        tmp=q.top();
        q.pop();

        if(vis[u])
        {
            continue;
        }
        vis[u]=true;

        for(ll i=0;i<G[u].size();i++)
        {
            if(dis[G[u][i].v]>dis[u]+G[u][i].w)
            {
                dis[G[u][i].v]=dis[u]+G[u][i].w;
                tmp.w=dis[G[u][i].v];
                tmp.v=G[u][i].v;
                q.push(tmp);
                pre[G[u][i].v]=u;
            }
        }
    }

    vector<ll> path;

    if(dis[n]<=b)
    {
        ll cur=n;
        while(pre[cur])
        {
            path.push_back(cur);
            cur=pre[cur];
        }
        path.push_back(1);

        ll ans=-1;

        for(auto i:path)
        {
            ans=max(ans,dq[i]);
        }

        printf("%lld\n",ans);
    }
    else 
    {
        // cout<<dis[n]<<endl;
        puts("AFK");
    }
}

int main()
{
    n=read();
    m=read();
    b=read();

    dq.resize(n+1);
    pre.resize(n+1);
    G.resize(n+1);

    for(ll i=1;i<=n;i++)
    {
        dq[i]=read();
    }

    for(ll i=1;i<=m;i++)
    {
        ll u=read();
        ll v=read();
        ll w=read();

        if(u==v)
        {
            continue;
        }

        G[u].push_back((node){v,w});
        G[v].push_back((node){u,w});
    }

    Dijksrta();

    // Debug
    // int Debuger=0;
    // cin>>Debuger;
    return 0;
}

by Texas_the_Omertosa @ 2023-01-09 08:17:55

@LeNotFound 这题不是要二分吗

by Moyou @ 2023-01-09 08:53:39

你这样最大值不一定是最小的

by Moyou @ 2023-01-09 08:57:58

Hack：

input

output

ans