currycodingg @ 2018-07-13 23:51:44
各位神犇们帮忙看一下好吗,就是一句话的事,导致我从WA了九个点到AC......
#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=10000+3;
const int M=50000+3;
const int INF=2147483646;
struct edge{
int v,c,next;//c为血量
}e[M*2];
int n,m,b,head[N],cnt,f[N],ff[N],d[N];//f[i]为费用(点权) ,d[i]为耗血(距离)
bool inq[N];
void addedge(int from,int to,int len){
e[++cnt]=(edge){to,len,head[from]}; head[from]=cnt;
}
bool SPFA(int topp){
//就是下面这句话!!!
//for(int i=1;i<=n;i++) d[i]=INF;// WA了九个点
memset(d,0x3f3f3f3f,sizeof(d)); //AC!!??
//这个INF的大小会对结果产生怎样的影响???求神犇指教qwq
memset(inq,false,sizeof(inq));
queue<int> Q;
Q.push(1); inq[1]=true; d[1]=0;
while(!Q.empty()){
int u=Q.front(); Q.pop(); inq[u]=false;
for(int i=head[u];i;i=e[i].next){
int v=e[i].v, c=e[i].c;
if(d[v]>d[u]+c && f[v]<=topp){
d[v]=d[u]+c;
if(!inq[v]){ Q.push(v); inq[v]=true; }
}
}
}
if(d[n]<=b) return true;
else return false;
}
int main(){
scanf("%d%d%d",&n,&m,&b);
for(int i=1;i<=n;i++){
scanf("%d",&f[i]); ff[i]=f[i];//SPFA时用f[] 二分时用ff[](先将ff[]排序) !!
}
int x,y,z;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&z);
addedge(x,y,z); addedge(y,x,z);
}
sort(ff+1,ff+n+1);
int maxx=ff[n];
//若点权为最大仍无法满足要求 则 AFK
if(SPFA(maxx+100)==false) {
printf("AFK\n"); return 0;
}
int l=1,r=n,mid;
int ans;
while(l<=r){ //二分的对象是点权
mid=(l+r)>>1;
if(SPFA(ff[mid])) { ans=ff[mid]; r=mid-1; }
else l=mid+1;
}
printf("%d\n",ans);
return 0;
}
多多指教,在下感激不尽qwq
by 小粉兔 @ 2018-07-14 01:05:05
inf设太大会爆int变成负数
by henry_y @ 2018-07-17 19:56:45
你inf设的是int的最大值,然后下面spfa的松弛操作是有加法的,加了就溢出了变成负数
改小一点就没什么问题了,比如1<<30什么的
by coyangjr @ 2018-07-18 14:31:14
推荐
const int INF = 0x3f3f3f3f ;
INF的大小为:1061109567
by wyyXHyzw @ 2018-07-24 12:37:48
如果有两个INF加起来比较会溢出变成负数
by currycodingg @ 2018-07-27 16:42:57
谢谢楼上各位神犇!