henry_y @ 2018-03-20 22:18:50
如题,各种修改之后一直都是输出6,哪位dalao帮忙看一下啊(感激不尽.jpg)
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define maxn 100100
#define inf 1<<30
#define mt(x,y) memset(x,y,sizeof(x))
#define max(x,y) x>y?x:y
#define min(x,y) x<y?x:y
#define abs(x) x>0?x:-x
#define mod 10000007
#define lowbit(x) x&-x
inline void read(int &x){x=0;int f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=f;}
using namespace std;
struct edge{int to,next,v;}e[maxn];
int head[maxn],cnt=1;
int n,m,b;
int f[maxn],p[maxn],vi[maxn],d[maxn],q[maxn];
inline void add(int u,int v,int w){e[++cnt].to=v;e[cnt].next=head[u];e[cnt].v=w;head[u]=cnt;}
inline void Add(int u,int v,int w){add(u,v,w);add(v,u,w);}
inline bool spfa(int top){
mt(vi,0);mt(d,inf);
int l=1,r=2,u,v;
q[1]=1;vi[1]=1;d[1]=0;
while(l<r){
u=q[l++];vi[u]=0;
for(int i=head[u];i;i=e[i].next){
v=e[i].to;
if(e[i].v+d[u]<d[v]&&f[e[i].to]<=top){
d[v]=e[i].v+d[u];
if(!vi[v]){
vi[v]=1;
q[r++]=v;
}
}
}
}
if(d[n]<=b)return 1;
else return 0;
}
int main(){
read(n);read(m);read(b);int u,v,w;
for(int i=1;i<=n;i++){read(f[i]);p[i]=f[i];}
for(int i=1;i<=m;i++){
read(u);read(v);read(w);
Add(u,v,w);
}sort(p+1,p+n+1);
int l=1,r=n,mid,ans=-1;
while(l<r){
mid=(l+r)/2;
if(spfa(p[mid])){
ans=p[mid];
r=mid-1;
}else l=mid+1;
}
if(ans==-1)printf("AFK");
else printf("%d",ans);
return 0;
}
by FrenzyHydra @ 2018-04-19 21:33:35
二分应该l<=r 我不会告诉你我这个错查了一天~~~~