哪位大佬进来看一下，谢谢！

秋水1024 @ 2020-04-06 13:47:22

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
struct line{
    long long to,w;
};
vector<line>a[10086];
struct node{
    long long p,num;
    friend bool operator<(node x,node y){
        return x.p>y.p;
    }
};
bool cmp(long long x,long long y){
    return x<y;
}
priority_queue<node>q;
long long n,m,k,f[10086],c[10086],dij[10086],u,v,w,minf,maxf;
bool b[10086];
bool dijkstra(long long x){
    memset(dij,63,sizeof(dij));
    memset(b,0,sizeof(b));
    for(long long i=1;i<=n;i++){
        if(f[i]>x)b[i]=true;
    }
    if(b[1]||b[n])return 0;
    dij[1]=0;
    b[1]=1;
    node t1;t1.p=1;t1.num=0;
    q.push(t1);
    while(!q.empty()){
        long long r=q.top().p;q.pop();
        b[r]=1;
        for(long long i=0;i<a[r].size();i++){
            long long l=a[r][i].to;
            if(dij[r]+a[r][i].w<dij[l]&&!b[l]){
                dij[l]=dij[r]+a[r][i].w;
                t1.p=l;t1.num=dij[l];
                q.push(t1);
            }
        }
    }
    //cout<<dij[0];
    if(dij[n]>k)return 0;
    else return 1;
}
int main()
{
    cin>>n>>m>>k;
    for(long long i=1;i<=n;i++){
        cin>>f[i];
        c[i]=f[i];
    }
    for(long long i=1;i<=m;i++){
        cin>>u>>v>>w;
        line t;t.to=v;t.w=w;
        a[u].push_back(t);
        t.to=u;
        a[v].push_back(t); 
    }   
    sort(c+1,c+n+1,cmp);
    if(!dijkstra(c[n])){
        cout<<"AFK";return 0;
    }
    long long l=1,r=n;
    while(l<r){
        long long mid=(l+r)/2;
        if(dijkstra(c[mid]))r=mid-1;
        else l=mid+1;
    }
    //if(l>maxf||r<minf||l<minf||r>maxf)cout<<"AFK";
    cout<<c[r];
    return 0;
}

by tommy0221 @ 2020-04-06 13:57:21

我会估计是您的二分炸了

by tommy0221 @ 2020-04-06 13:59:04

建议换一种写法：

int l=左边界，r=右边界,mid,res;
while(l<=r) {
    mid=(l+r)>>1;
    if(c[mid]满足条件)res=mid,r=mid-1;
    else l=mid+1;
}
cout<<c[res]<<endl;

by tommy0221 @ 2020-04-06 13:59:23

@mmy20051024

by 秋水1024 @ 2020-04-06 22:02:07

谢谢巨佬，膜拜膜拜

by 秋水1024 @ 2020-04-06 22:17:34

哎呀，第8个AFK了

悲催的链接

有点尴尬啊。

附巨佬指正后的代码

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
struct line{
    long long to,w;
};
vector<line>a[10086];
struct node{
    long long p,num;
    friend bool operator<(node x,node y){
        return x.p>y.p;
    }
};
bool cmp(long long x,long long y){
    return x<y;
}
priority_queue<node>q;
long long n,m,k,f[10086],c[10086],dij[10086],u,v,w,minf,maxf;
bool b[10086];
bool dijkstra(long long x){
    memset(dij,63,sizeof(dij));
    memset(b,0,sizeof(b));
    for(long long i=1;i<=n;i++){
        if(f[i]>x)b[i]=true;
    }
    if(b[1]||b[n])return 0;
    dij[1]=0;
    b[1]=1;
    node t1;t1.p=1;t1.num=0;
    q.push(t1);
    while(!q.empty()){
        long long r=q.top().p;q.pop();
        b[r]=1;
        for(long long i=0;i<a[r].size();i++){
            long long l=a[r][i].to;
            if(dij[r]+a[r][i].w<dij[l]&&!b[l]){
                dij[l]=dij[r]+a[r][i].w;
                t1.p=l;t1.num=dij[l];
                q.push(t1);
            }
        }
    }
    //cout<<dij[0];
    if(dij[n]>k)return 0;
    else return 1;
}
int main()
{
    cin>>n>>m>>k;
    for(long long i=1;i<=n;i++){
        cin>>f[i];
        c[i]=f[i];
    }
    for(long long i=1;i<=m;i++){
        cin>>u>>v>>w;
        line t;t.to=v;t.w=w;
        a[u].push_back(t);
        t.to=u;
        a[v].push_back(t); 
    }   
    sort(c+1,c+n+1,cmp);
    if(!dijkstra(0x3f3f3f3f)){
        cout<<"AFK";return 0;
    }
    long long l=1,r=n,res;
    while(l<=r){
        long long mid=(l+r)/2;
        if(dijkstra(c[mid])){
        r=mid-1;res=mid;}
        else l=mid+1;
    }
    cout<<c[res];
    return 0;
}

这回不会是最短路崩盘了吧

by 秋水1024 @ 2020-08-06 20:36:06

return x.p>y.p;

应改为

return x.num>y.num;

by 秋水1024 @ 2020-08-06 20:36:47

完结撒花，慢走不送（话说我自己与自己较什么劲）