各位大佬，可否帮忙解决一下蒟蒻的题？WA两个点

M_and_P_ @ 2020-08-07 20:20:47

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#define N 10005
#define MAXN 1000000005 
using namespace std;
struct node{
    int num,cost,bloom;
    bool operator<(const node&rhs)const{
        return cost>rhs.cost;
    }
}vex;
int n,m,B;
int V[N],dis[N];
bool vis[N];
vector<node>G[N];
priority_queue<node>pq;
bool check(int level)
{
    if (V[1]>level||V[n]>level)return false;

    node vex;
    vex.num=1;vex.cost=dis[1];vex.bloom=B;
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[1]=V[1];
    pq.push(vex);
    while(!pq.empty())
    {
        node h=pq.top();pq.pop();
        int num=h.num;
        if (vis[num])continue;
        vis[num]=true;
        for (int i=0;i<G[num].size();i++)
        {
            node j=G[num][i];
            if (!vis[j.num] && h.bloom>=j.bloom && j.cost<=level)
            {
                dis[j.num]=max(j.cost,h.cost);
                vex.num=j.num;
                vex.cost=dis[j.num];
                vex.bloom=h.bloom-j.bloom;
                pq.push(vex);
            }
        }
    }
    return dis[n]<=level;
}
int main()
{
    scanf("%d%d%d",&n,&m,&B);
    for (int i=1;i<=n;i++){
        scanf("%d",&V[i]);
    }
    int u,v,bloom,l,r;
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&bloom);
        vex.num=u;vex.cost=V[v];vex.bloom=bloom;
        G[v].push_back(vex);
        vex.num=v;vex.cost=V[u];
        G[u].push_back(vex);
    }
    l=0;r=MAXN;
    int mid;
    while(l<r)
    {
        mid=(l+r)/2;
        if (check(mid))r=mid;
        else l=mid+1;
    }
    if (r==MAXN)puts("AFK");
    else printf("%d",l);
    return 0;
}

by 那一条变阻器 @ 2020-08-07 20:39:35

应该跑消耗血量最短路

by 那一条变阻器 @ 2020-08-07 20:40:27

@NOIP_AK 跑费用最短路的话，每次求max会反而得出最大的值

by 那一条变阻器 @ 2020-08-07 20:42:08

改成血量最短路，每次求一下可行的最小费用即可

by 那一条变阻器 @ 2020-08-07 20:42:22

@NOIP_AK

by M_and_P_ @ 2020-08-07 21:08:22

@那一条变阻器 万分感谢(⊙o⊙)

Orz Orz Orz Orz Orz Orz Orz Orz Orz Orz Orz

Orz Orz Orz Orz Orz Orz Orz Orz Orz Orz Orz

Orz Orz Orz Orz Orz Orz Orz Orz Orz Orz Orz

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

果真巨佬！！巨佬，我们交个朋友吧！

说的一点没错！

此题花了我一个小时，终于AC了，耶！

附上AC代码表示纪念：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#define N 10005
#define MAXN 1000000005 
using namespace std;
struct node{
    int num,cost,bloom;
    bool operator<(const node&rhs)const{
        return bloom>rhs.bloom;
    }
}vex;
int n,m,B;
int V[N],dis[N],mindis[N];
bool vis[N];
vector<node>G[N];
priority_queue<node>pq;
bool check(int level)
{
    if (V[1]>level||V[n]>level)return false;

    node vex;
    vex.num=1;vex.cost=dis[1];vex.bloom=0;
    memset(dis,0x3f,sizeof(dis));
    memset(mindis,0x3f,sizeof(mindis));
    memset(vis,0,sizeof(vis));
    dis[1]=0;
    pq.push(vex);
    while(!pq.empty())
    {
        node h=pq.top();pq.pop();
        int num=h.num;
        if (vis[num])continue;
        vis[num]=true;
        for (int i=0;i<G[num].size();i++)
        {
            node j=G[num][i];
            if (!vis[j.num] && dis[j.num]>dis[h.num]+j.bloom && dis[h.num]+j.bloom<B && j.cost<=level)
            {
                dis[j.num]=dis[h.num]+j.bloom;
                vex.num=j.num;
                vex.cost=max(j.cost,V[j.num]);
                mindis[vex.num]=min(mindis[vex.num],vex.cost);
                vex.bloom=dis[j.num];
                pq.push(vex);
            }
        }
    }
    return mindis[n]<=level;
}
int main()
{
    scanf("%d%d%d",&n,&m,&B);
    for (int i=1;i<=n;i++){
        scanf("%d",&V[i]);
    }
    int u,v,bloom,l,r;
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&bloom);
        vex.num=u;vex.cost=V[v];vex.bloom=bloom;
        G[v].push_back(vex);
        vex.num=v;vex.cost=V[u];
        G[u].push_back(vex);
    }
    l=0;r=MAXN;
    int mid;
    while(l<r)
    {
        mid=(l+r)/2;
        if (check(mid))r=mid;
        else l=mid+1;
    }
    if (r==MAXN)puts("AFK");
    else printf("%d",l);
    return 0;
}

by 那一条变阻器 @ 2020-08-07 21:43:07

@NOIP_AK 我是菜鸡/kk