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 十分感谢老铁,问题已经解决~你的书也写的不错,下载下来拜读一下,蟹蟹