90pts 求调Wa#8

chenyizhen @ 2024-10-24 14:24:25

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int M=1e5+5,N=1e4+5,inf=2147483647;
struct edge{
    int start,end,c;
}e[M];
int n,m,b;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
int dis[N],vis[N];
int cost[N];
int head[M],cnt=0;
inline void add(int u,int v,int c){
    e[++cnt].end=v;
    e[cnt].start=head[u];
    head[u]=cnt;
    e[cnt].c=c;
}

int dijkstra(int money){
    for(int i=1;i<=n;i++){
        dis[i]=1e9;vis[i]=0;
    }
    dis[1]=0;
    if(money<cost[1]) return 0;
    q.push(make_pair(dis[1],1));
    while(!q.empty()){
        int u=q.top().second;
        q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=head[u];i;i=e[i].start){
            int v=e[i].end;
            if(cost[v]>money) continue;
//          if(vis[v]) continue;
            if(dis[v]>dis[u]+e[v].c&&vis[v]==0){
                dis[v]=dis[u]+e[v].c;
                q.push(make_pair(dis[v],v));
            }
        }
    }
//  cout<<dis[n];
    if(dis[n]<=b){      
        return 1;
    }else{
        return 0;
    }

}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
//  freopen("","r")
    int u,v,c;
    int l=0,r=0;
    cin>>n>>m>>b;
    for(int i=1;i<=n;i++){
        cin>>cost[i];
        r=max(r,cost[i]);
    }
    for(int i=1;i<=m;i++){
        cin>>u>>v>>c;
        add(u,v,c);
        add(v,u,c);
    }
    r=1000000005;
    if(dijkstra(r)==0){
        cout<<"AFK";
        return 0;
    }   
    while(l<r){
        int mid=(l+r)/2;
        if(dijkstra(mid)==0){
            l=mid+1;
        }else{
            r=mid;
        }   
    }
    cout<<l;

    return 0;
}

by doooge @ 2024-10-24 14:28:34

@chenyizhen 把36行的 &&vis[v]==0 去掉试试

by chenyizhen @ 2024-10-24 14:53:28

@doooge 谢谢，但还还是wa

by WvWeet @ 2024-10-25 11:24:00

兄弟是不是你链式前向星写的有问题啊，我改成邻接表就过了

by WvWeet @ 2024-10-25 11:24:33

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int M=1e5+5,N=1e4+5,inf=2147483647;
struct edge{
    int start,end,c;
}e[M];
int n,m,b;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
int dis[N],vis[N];
int cost[N];
int head[M],cnt=0;
vector<pair<int,int>> g[N]; 

int dijkstra(int money){
    for(int i=1;i<=n;i++){
        dis[i]=1e9;vis[i]=0;
    }
    dis[1]=0;
    if(money<cost[1]) return 0;
    q.push(make_pair(dis[1],1));
    while(!q.empty()){
        int u=q.top().second;
        q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(auto [v,w]:g[u]){
            if(cost[v]>money) continue;
//          if(vis[v]) continue;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                q.push(make_pair(dis[v],v));
            }
        }
    }
//  cout<<dis[n];
    if(dis[n]<=b){      
        return 1;
    }else{
        return 0;
    }

}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
//  freopen("","r")
    int u,v,c;
    int l=0,r=0;
    cin>>n>>m>>b;
    for(int i=1;i<=n;i++){
        cin>>cost[i];
        r=max(r,cost[i]);
    }
    for(int i=1;i<=m;i++){
        cin>>u>>v>>c;
        g[u].push_back({v,c});
        g[v].push_back({u,c});
    }
    r=1000000005;
    if(dijkstra(r)==0){
        cout<<"AFK";
        return 0;
    }   
    while(l<r){
        int mid=(l+r)/2;
        if(dijkstra(mid)==0){
            l=mid+1;
        }else{
            r=mid;
        }   
    }
    cout<<l;

    return 0;
}