被Dij搞崩Day3，求调，目前超时

P1462 通往奥格瑞玛的道路

3a51_ @ 2022-03-04 17:49:26

/*
work by:Tothetime_tolife
time:1s
space:128MB
*/
#include<bits/stdc++.h>
#define int long long
#define Tothetime_tolife using
#define AK namespace
#define IOI std
Tothetime_tolife AK IOI;
const int Mod1=998244353;
const int Mod2=1000000007;
int gcd(int a,int b){return __gcd(a,b);}
int lcm(int a,int b){return a*b/gcd(a,b);}
int qpow(int a,int b){int res=1;while(b){if(b&1){res=res*a%Mod1;}b>>=1;a=a*a%Mod1;}return res%Mod1;}
template <typename T> inline void read(T& x) {
    x=0;T f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=x*f;
    return;
}
template <typename T,typename ...Arg>void read(T& x,Arg& ...arg){
    read(x);
    read(arg...);
}
template <typename T>void write(T x) {
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+'0');
    else write(x/10),putchar(x%10+'0');
}
template <typename T,typename ...Arg>void write(T& x,Arg& ...arg){
    write(x);
    putchar(' ');
    write(arg...);
}
const int N=2505;
const int M=6205;
const int Max=2147483647;
int n,m,l,S,T,b,ans,dis[N],f[N],head[N],cnt,x,y,z,t,Cnt=1;
int to[2*M],nxt[2*M],val[2*M],X[2*M],Y[2*M],Z[2*M];
bool vis[N];
struct Node{
    int id,w;
    friend bool operator<(const Node A,const Node B){
        return A.w>B.w;
    }
};
inline void add(int u,int v,int w){
    to[++cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
    val[cnt]=w;
    return;
}
priority_queue<Node> Q;
int dij(int sx){
    for(int i=1;i<=n;i++) dis[i]=Max;
    Node now;
    now.id=S;now.w=0;
    dis[S]=0;
    int p,ww;
    Q.push(now);
    memset(vis,0,sizeof(vis));
    while(!Q.empty()){
        Node x=Q.top();
        Q.pop();
        p=x.id;
        ww=x.w;
        if(vis[p] || dis[p]!=ww){
            continue;
        }
        vis[p]=1;
        int u;
        for(register int i=head[p];f[to[i]]<=sx;i=nxt[i]){
            u=to[i];
            if(dis[p]+val[i]<dis[u]){
                dis[u]=dis[p]+val[i];
                now.id=u;now.w=dis[u];
                Q.push(now);
            }
        }
    }
    if(dis[n]<b){
        return 1;
    }
    return 0;
}
signed main()
{
    //;;;;;
    read(n,m,b);
    S=1;
    for(int i=1;i<=n;i++){
        read(f[i]);
    }
    for(int i=1;i<=m;i++){
        read(x,y,z);
        add(x,y,z);
        add(y,x,z);
    }
    int l=0,r=100000005,mid;
    while(l<=r){
        mid=(l+r)>>1;
        //cout<<l<<" "<<r<<endl;
        if(dij(mid)){
            r=mid-1;
        }
        else{
            l=mid+1;
        }
    }
    cout<<l;
    return 0;
}
//QwQ

又被最短路搞崩了QwQ，求调。希望别再被抓住。

by Enterprise_E @ 2022-03-04 18:25:04

@Tothetime_tolife

DJI（大疆）:好家伙我成那啥了……

by pengzy___ @ 2022-03-04 18:51:05

~~二分难道不比最短路难么？？？~~

by TheSky233 @ 2022-03-04 19:10:55

for(register int i=head[p];f[to[i]]<=sx;i=nxt[i]){这一行有问题，应该在循环里面判断f[to[i]]是否小于等于sx，否则有一个大于就直接退出循环了。
struct要多维护一个left域，作为走到当前节点的剩余血量。如果维护了这个，当 p=n 是就可以 return true 了。
~~为什么 Dij 不定义成 bool~~。

见代码

/*
work by:Tothetime_tolife
time:1s
space:128MB
*/
#include<bits/stdc++.h>
#define int long long
#define Tothetime_tolife using
#define AK namespace
#define IOI std
Tothetime_tolife AK IOI;
const int Mod1=998244353;
const int Mod2=1000000007;
int gcd(int a,int b){return __gcd(a,b);}
int lcm(int a,int b){return a*b/gcd(a,b);}
int qpow(int a,int b){int res=1;while(b){if(b&1){res=res*a%Mod1;}b>>=1;a=a*a%Mod1;}return res%Mod1;}
template <typename T> inline void read(T& x) {
    x=0;T f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=x*f;
    return;
}
template <typename T,typename ...Arg>void read(T& x,Arg& ...arg){
    read(x);
    read(arg...);
}
template <typename T>void write(T x) {
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+'0');
    else write(x/10),putchar(x%10+'0');
}
template <typename T,typename ...Arg>void write(T& x,Arg& ...arg){
    write(x);
    putchar(' ');
    write(arg...);
}
const int N=2505;
const int M=6205;
const int Max=2147483647;
int n,m,l,S,T,b,ans,dis[N],f[N],head[N],cnt,x,y,z,t,Cnt=1;
int to[2*M],nxt[2*M],val[2*M],X[2*M],Y[2*M],Z[2*M];
bool vis[N];
struct Node{
    int id,w,left;
    friend bool operator<(const Node A,const Node B){
        return A.w>B.w;
    }
};
inline void add(int u,int v,int w){
    to[++cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
    val[cnt]=w;
    return;
}
priority_queue<Node> Q;
bool dij(int sx){
    for(int i=1;i<=n;i++) dis[i]=Max;
    Node now;
    now.id=S;now.w=0;now.left=b;
    dis[S]=0;
    int p,ww;
    Q.push(now);
    memset(vis,0,sizeof(vis));
    while(!Q.empty()){
        Node x=Q.top();
        Q.pop();
        p=x.id;
        ww=x.w;
        if(p==n) return true;
        if(vis[p]){
            continue;
        }
        vis[p]=1;
        int u;
        for(register int i=head[p];i;i=nxt[i]){
            u=to[i];
            if(dis[p]+val[i]<dis[u] && f[u]<=sx && x.left-val[i]>=0){
                dis[u]=dis[p]+val[i];
                now.id=u;now.w=dis[u];now.left=x.left-val[i];
                Q.push(now);
            }
        }
    }
    return 0;
}
signed main()
{
    //;;;;;
    int l,r,mid,ans=0;
    read(n,m,b);
    S=1;
    for(int i=1;i<=n;i++){
        read(f[i]); r=max(r,f[i]);
    }
    for(int i=1;i<=m;i++){
        read(x,y,z);
        add(x,y,z);
        add(y,x,z);
    }
    l=f[1]; 
    while(l<=r){
        mid=(l+r)>>1;
        //cout<<l<<" "<<r<<endl;
        if(dij(mid)){
            ans=mid;
            r=mid-1;
        }
        else{
            l=mid+1;
        }
    }
    if(!ans) cout<<"AFK";
    else cout<<ans;
    return 0;
}
//QwQ

话说我今天正好 AC 了这道 QwQ

by StarLbright40 @ 2022-03-04 19:42:00

楼上提到的 left 和最后判 dis[n]<=b 是两种不同的实现方法，即在过程中判断和在结果处判断，选一个即可。

另外，由题意可知如果他的血量刚好降至 0，也是可行的，所以应为 dis[n]<=0。

另外，楼主的二分大有问题（

上一页 |