只有三个AFK的点是对的,找不出来哪里错的哭~~

P1462 通往奥格瑞玛的道路

hey_friend @ 2020-04-03 22:51:56

本蒟蒻真的找不出来,虽然没用什么复杂的优化,就简单用了个优先级队列+dj+二分,实在找不出哪里错的,测试样例倒是对的,求求大佬帮帮忙

#include<bits/stdc++.h>
using namespace std;
int n,m,b;
const int INF=1000000000;
int fee[10001];
struct node{
    int v,w;
    node(int _v,int _w){
        v=_v;
        w=_w;
    }
};
vector<node> g[10001]; 
bool vis[10001];
long long d[10001];
struct cmp{
    bool operator()(int a,int b){
        return d[a]>d[b];
    }
};
priority_queue<int,vector<int>,cmp> p;//以编号入队列,因为不会重复的 

bool  dj(int s,int money,int hp){
    fill(d,d+10001,INF);
    fill(vis,vis+10001,false);
    d[s]=0;
    p.push(s);
    while(!p.empty()){
        int u=p.top();
        p.pop();
        vis[u]=true;//只有选出最小的那个才算是访问过 
        for(int j=0;j<g[u].size();j++){
            int v=g[u][j].v;
            if(vis[v]==false&&d[u]+g[u][j].w<d[v]&&fee[v]<=money){
                d[v]=d[u]+g[u][j].w;
                p.push(v);
            }
        }
    }

    return d[n]<hp;
} 

int main(){

    scanf("%d%d%d",&n,&m,&b);
    for(int i=1;i<=n;i++)
       scanf("%d",&fee[i]);
    for(int i=1;i<=m;i++){
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        g[a].push_back(node(b,w));
        g[b].push_back(node(a,w));
    }
    sort(fee+1,fee+n+1);//排序,准备采用二分法 
   int left=1,right=n;
   int ans=0;
   if(!dj(1,INF,b)){
    printf("AFK");
   return 0;
   }
   while(left<=right){
    int mid=(left+right)/2;
    if(dj(1,fee[mid],b)){//参与比较的中间的那个费用,而不是mid这个序号 
        ans=fee[mid];
        right=mid-1;
    }
    else{
        left=mid+1;
    }
   }
   cout<<ans;

} 

by JeffWang2019 @ 2020-04-03 23:12:41

试试下载数据?


by metaphysis @ 2020-04-04 08:14:30

@hey_friend

阅读了您的代码,发现至少有两个错误。 (1)题目约束要求起点和终点都要收费,但在您的代码中未见到对起点收费进行检查,假设起点都超过给定的money,则不可能到达终点。 (2)因为您认为您的解题思路是正确的(的确,思路是正确的),但是在实现时出现了一个致命的逻辑错误,不过由于您已经落入了“思维陷阱”,很难发现。Bug提示:您的代码中对每个顶点的费用进行了排序,在更新最短路径时却用初始建图时的顶点序号去获取费用值,是否可以这样做呢?

建议您更改上述错误后再尝试提交,如果不能Accepted,欢迎您@我。

有空请您访问我的 CSDN博客,里面有我写的一本书,内有编程竞赛相关内容的介绍,并附有对应的练习题目(题目源自UVa OJ),可免费下载此书的PDF版本:《C++,挑战编程——程序设计竞赛进阶训练指南》。可以的话,还烦您向对编程感兴趣的朋友推荐一下我的博客和书,感谢!


by hey_friend @ 2020-04-04 23:15:54

@metaphysis 十分感谢老铁,问题已经解决~你的书也写的不错,下载下来拜读一下,蟹蟹


|