求助大佬
  • 板块P3403 跳楼机
  • 楼主Kniqht
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/10/17 21:28
  • 上次更新2023/10/27 07:04:37
查看原帖
求助大佬
315205
Kniqht楼主2022/10/17 21:28

简单最短路90pts调了半天了,没看出问题啊

#include<bits/stdc++.h>
#define int long long
#define ll unsigned long long
using namespace std;
const int N=4e5+10,inf=0x3f3f3f3f;
int h[N],e[N],ne[N],idx,q[N],hh,tt;
ll n,x,y,z,dist[N],w[N],ans;
bool st[N];
void add(int a,int b,ll c){e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;}
void SPFA(){
    memset(dist,inf,sizeof(dist));
    q[0]=1;st[1]=true;dist[1]=0;
    while(hh<=tt){
        int t=q[hh++];st[t]=false;
        for(int i=h[t];~i;i=ne[i]){
            int j=e[i];
            if(dist[j]>dist[t]+w[i]){
                dist[j]=dist[t]+w[i];
                if(!st[j])q[++tt]=j,st[j]=true;
            }
        }
    }
    for(int i=0;i<x;i++) 
        if(n>=dist[i]) ans+=(n-dist[i])/x+1;
    printf("%llu",ans);
}
signed main(){
    memset(h,-1,sizeof(h));
    scanf("%llu%llu%llu%llu",&n,&x,&y,&z);n--;
    if(x==1||y==1||z==1){printf("%llu",n);return 0;}
    for(int i=0;i<x;i++) add(i,(i+y)%x,y),add(i,(i+z)%x,z);
    SPFA();
    return 0;
}
2022/10/17 21:28
加载中...