人中 @ 2019-08-23 21:53:00
int check(int x) {
if(x<money[1])
return 0;
for(int i=1; i<=n; i++) {
dist[i]=0x3f3f3f3f3f;
}
dist[1]=0;
Q.push((node) {
1,0
});
while(!Q.empty()) {
node fr=Q.top();
Q.pop();
int d=fr.d;
int u=fr.u;
if(dist[u]!=d)
continue;
for(int i=head[u]; i; i=edge[i].next) {
if(dist[edge[i].to]>edge[i].dis+dist[u]&&money[edge[i].to]<=x) {
dist[edge[i].to]=edge[i].dis+dist[u];
Q.push((node {edge[i].to,dist[edge[i].to]}));
}
if(edge[i].to==n) {
if(dist[n]<=hp)
return 1;
else
return 0;
}
}
}
}
while(l<r){
int mid=(l+r)>>1;
if(check(mid)==1) {r=mid;kl=1;
}
else l=mid+1;
}
if(kl==0){
cout<<"AFK";
}else
cout<<l;
}
这是我的二分和check函数
为什么 我将
for(int i=head[u]; i; i=edge[i].next) {
if(dist[edge[i].to]>edge[i].dis+dist[u]&&money[edge[i].to]<=x) {
写成
for(int i=head[u]; i; i=edge[i].next) {
if(money[i]>x)
continue;
if(dist[edge[i].to]>edge[i].dis+dist[u]) {
就错了
麻烦@一下我,蟹蟹
by 顾小伍 @ 2019-08-26 20:26:28
@人中 i表示的是这条边指向的节点位置,不能直接表示所指的节点,所以要把i改成edge[i].to,这是链式前向星的基本常识。最后安利一波我的博客,喜欢可以点个赞~(≧▽≦)/~
by 人中 @ 2019-08-26 20:38:52
@顾小伍 啊啊蟹蟹,错误好低级,丢脸
by 顾小伍 @ 2019-08-26 20:44:21
@人中 初学是比较容易错,很正常的事