10RE1AC求助,大佬能看出我的问题吗

P1462 通往奥格瑞玛的道路

粉刷匠 @ 2020-02-25 00:30:24

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int const inf=1000000010;
int n,m,b;
int f[10005];
int f1[10005];
int dis[10005];
int flag=1;
struct edge
{
    int to,cost;
};
vector<edge>g[10005];
struct node
{
    int u,d;
    bool operator<(const node&a)const
    {
        return d>a.d;
    }
};
inline bool djs(int x)
{
    if(x<f1[1]||x<f1[n])
    return false;

    for(int i=1;i<=b;i++)
        dis[i]=inf;
    dis[1]=0;
    priority_queue<node>Q;

    node a={1,0};
    Q.push(a);

    while(!Q.empty())
    {
        node fr=Q.top();Q.pop();
        int u=fr.u,d=fr.d;
        if(d!=dis[u])continue;
        if(u==n)continue;
        for(int j=0;j<g[u].size();j++)
        {
            int tm=g[u][j].to;
            if(f1[tm]>x)continue;
            if(dis[u]+g[u][j].cost<dis[tm])
            {            
                dis[tm]=dis[u]+g[u][j].cost;
                Q.push((node){tm,dis[tm]});
            }
        }
    }
    return dis[n]<=b;
} 
int main()
{
  scanf("%d%d%d",&n,&m,&b);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&f[i]);
        f1[i]=f[i];
    }
    sort(f+1,f+1+n);
    edge temp;
    for(int i=1;i<=m;i++)
    {
        int x,y,cost;
        scanf("%d%d%d",&x,&y,&cost);
        temp.cost=cost;
        temp.to=y;
        g[x].push_back(temp);
        temp.to=x;
        g[y].push_back(temp);
    }
    if(!djs(f[n]))
    {
        printf("AFK\n");
        return 0;
    }
    int l=1,r=n,mid;
    int ans=f[n];
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(djs(f[mid]))
        {
            ans=f[mid];
            r=mid-1;
        }
        else l=mid+1;
    }
    printf("%d\n",ans);
/// printf("%d",ans);
    return 0;
}

by 几何之舞丶 @ 2020-02-25 07:38:14

inf 开太大了.

dij的时候没有开个vis数组记录哪些边访问过,


by 粉刷匠 @ 2020-02-25 09:21:15

问题解决了谢谢


|