gjh303987897 @ 2019-08-28 11:52:21
#include<bits/stdc++.h>
#define maxn 10001
using namespace std;
priority_queue<pair<int ,int> >q;
inline int read()
{
int x=0; int f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
{
f=-1;
}
ch=getchar();
}
while(ch<='9'&&ch>='0')
{
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x*f;
}
struct data
{
int dis;
int to;
int next;
}a[100010];
int n,m,b;
int fa[maxn],f[maxn];
int bs,head[maxn];
int er[maxn],ans;
inline void add(int x,int y,int z)
{
bs++;
a[bs].dis=head[x];
a[bs].dis=z;
a[bs].to=y;
head[x]=bs;
}
int dist[maxn];
int flag[maxn];
int cheak(int fy)
{
memset(dist,100000000,sizeof(dist));
for(int i=1;i<=n;i++)
{
if(er[i]>fy) flag[i]=1;
}
dist[1]=0;
q.push(make_pair(0,1));
while(q.size())
{
int x=q.top().second;q.pop();
if(flag[x]==1) continue;
flag[x]=1;
for(int i=head[x];i!=0;i=a[i].next)
{
int y=a[i].next; int z=a[i].dis;
if(dist[y]>dist[x]+z)
{
dist[y]>dist[x]+z;
q.push(make_pair(-dist[y],y));
}
}
}
if(dist[n]>b)
{
return 2;
}else
{
return 1;
}
}
int find(int x)
{
if(fa[x]!=x)
{
fa[x]=find(fa[x]);
}
return fa[x];
}
int main()
{
n=read(); m=read(); b=read();
for(int i=1;i<=n;i++)
{
f[i]=read();
er[i]=f[i];
}
for(int i=1;i<=n;i++)
{
fa[i]=i;
}
for(int i=1;i<=m;i++)
{
int x,y,z;
x=read(); y=read(); z=read();
add(x,y,z);
add(y,x,z);
fa[y]=x;
}
int c1=find(1);
int c2=find(n);
if(c1!=c2)
{
cout<<"AFK";
return 0;
}
sort(er+1,er+1+n);
int r=n,l=1;
int mid=(l+r)>>1;
while(l<=r)
{
if(cheak(er[mid])==2)//no
{
r=mid-1;
mid=(l+r)>>1;
}else
{
ans=mid;
l=mid+1;
mid=(l+r)>>1;
}
}
cout<<er[ans];
return 0;
}by 0nullptr @ 2019-08-28 11:54:50
@gjh303987897 memset函数不是像你想象的那样赋值的。如果你想为数组赋一个极大值，最好写memset(dist,0x3f,sizeof(dist));
by 常青藤 @ 2019-08-28 12:06:43
int y=a[i].next; int z=a[i].dis;
if(dist[y]>dist[x]+z)
{
dist[y]>dist[x]+z;
q.push(make_pair(-dist[y],y));
}这里的y是a[i].to
其他的还没有看
by OvOAuto @ 2019-08-28 12:12:36
我们机房赋值max都是memset(a,999999,sizeof(a));
by OvOAuto @ 2019-08-28 12:14:02
1e6 - 1是个比较巧的数
记得正好就可以到2e9的水平
by gjh303987897 @ 2019-08-28 12:21:31
@常青藤 谢谢，手残了
by gjh303987897 @ 2019-08-28 12:23:43
@常青藤 但是改完了我交了一遍结果还是一样
by gjh303987897 @ 2019-08-28 12:27:15
@zs__std 知道了，谢谢
by 常青藤 @ 2019-08-28 12:37:24
貌似有几处手残错误（改了可以通过样例）
#include<bits/stdc++.h>
#define maxn 10001
using namespace std;
priority_queue<pair<int ,int> >q;
inline int read()
{
int x=0; int f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
{
f=-1;
}
ch=getchar();
}
while(ch<='9'&&ch>='0')
{
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x*f;
}
struct data
{
int dis;
int to;
int next;
}a[100010];
int n,m,b;
int fa[maxn],f[maxn];
int bs,head[maxn];
int er[maxn],ans;
inline void add(int x,int y,int z)
{
bs++;
a[bs].dis=head[x]; ////此处为a[bs].next
a[bs].dis=z;
a[bs].to=y;
head[x]=bs;
}
int dist[maxn];
int flag[maxn];
int cheak(int fy)
{
memset(dist,100000000,sizeof(dist)); ////100000000->0x3f
/////添加if(fy<er[1] || fy<er[n]) return 2; (连起点和终点都到不了)
for(int i=1;i<=n;i++)
{
if(er[i]>fy) flag[i]=1;
}
dist[1]=0;
q.push(make_pair(0,1));
while(q.size())
{
int x=q.top().second;q.pop();
if(flag[x]==1) continue;
flag[x]=1;
for(int i=head[x];i!=0;i=a[i].next)
{
int y=a[i].next; int z=a[i].dis;// next->to
if(dist[y]>dist[x]+z)
{
dist[y]>dist[x]+z;////> -> =
q.push(make_pair(-dist[y],y));
}
}
}
if(dist[n]>b)
{
return 2;
}else
{
return 1;
}
}
int find(int x)
{
if(fa[x]!=x)
{
fa[x]=find(fa[x]);
}
return fa[x];
}
int main()
{
n=read(); m=read(); b=read();
for(int i=1;i<=n;i++)
{
f[i]=read();
er[i]=f[i];
}
for(int i=1;i<=n;i++)
{
fa[i]=i;
}
for(int i=1;i<=m;i++)
{
int x,y,z;
x=read(); y=read(); z=read();
add(x,y,z);
add(y,x,z);
fa[y]=x;
}
int c1=find(1);
int c2=find(n);
if(c1!=c2)
{
cout<<"AFK";
return 0;
}
sort(er+1,er+1+n);
int r=n,l=1;
int mid=(l+r)>>1;
while(l<=r)
{
if(cheak(er[mid])==2)//no
{
r=mid-1; ////l=mid+1;
mid=(l+r)>>1;
}else
{
ans=mid;
l=mid+1; ////r=mid-1;
mid=(l+r)>>1;
}
}
cout<<er[ans];
return 0;
}by 常青藤 @ 2019-08-28 12:38:42
不过我没(bu)有(gan)帮你提交
我做这题时就调了很长很长时间
by 常青藤 @ 2019-08-28 12:40:43
顺便放一份我的
#include<bits/stdc++.h>
#define in(x) x=read()
using namespace std;
const int maxN=100000,maxM=200000;
inline int read()
{
int n=0; char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) {n=n*10+ch-'0'; ch=getchar();}
return n;
}
int head[maxN+1],n,m,b,tot,ans=-1,l,r;
long long dis[maxN+1];
int f[maxN+1],a[maxN+1],vis[maxN+1];
struct Node{int to,next,value;}edge[maxM+1];
priority_queue<pair<int,int> > q;
void addedge(int x,int y,int value)
{
edge[++tot].to=y;
edge[tot].value=value;
edge[tot].next=head[x];
head[x]=tot;
}
bool dijkstra(int x,int s)
{
if(x<f[1] || x<f[n]) return false;
for(int i=1;i<=maxN;i++) dis[i]=INT_MAX;
for(int i=1;i<=n;i++) vis[i]=(f[i]>x);
dis[s]=0; q.push(make_pair(0,s));
while(!q.empty())
{
int x=q.top().second; q.pop();
if(vis[x]) continue; vis[x]=1;
for(int i=head[x];i;i=edge[i].next)
if(dis[edge[i].to]>dis[x]+edge[i].value)
{
dis[edge[i].to]=dis[x]+edge[i].value;
q.push(make_pair(-dis[edge[i].to],edge[i].to));
}
}
return (dis[n]<=b);
}
int main()
{
in(n); in(m); in(b);
for(int i=1;i<=n;i++) a[i]=f[i]=read();
for(int i=1;i<=m;i++)
{
int x,y,z; in(x); in(y); in(z);
if(x==y) continue;
addedge(x,y,z); addedge(y,x,z);
}
sort(a+1,a+n+1); l=1; r=n; ans=a[n];
if(!dijkstra(a[n],1)) {printf("AFK"); return 0;}
while(l<=r)
{
int mid=(l+r>>1);
if(dijkstra(a[mid],1)) {ans=a[mid]; r=mid-1;}
else l=mid+1;
}
printf("%d",ans);
return 0;
}