萌新求助40分dij死了
  • 板块P3403 跳楼机
  • 楼主Baizhuo
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/7/1 09:47
  • 上次更新2023/11/3 12:00:41
查看原帖
萌新求助40分dij死了
643856
Baizhuo楼主2023/7/1 09:47
#include <bits/stdc++.h>
#define int long long
using namespace std ;
int maxd ;
int x , y , z ;
const int N = 3e5 + 10 ;
int h[N] , e[N] , ne[N] , w[N] , idx ;
int f[N] ;

void add(int a , int b , int c) {
    e[idx] = b , ne[idx] = h[a] , w[idx] = c , h[a] = idx ++ ;
}

typedef pair<int , int> PII ;
bool st[N] ;

void dijkstra() {
    memset(f , 0x3f , sizeof f) ;
    priority_queue<PII , vector<PII> , greater<PII> >heap ;
    f[1] = 1 ;
    heap.push({1 , 1}) ;
    while (heap.size()) {
        PII t = heap.top() ;
        heap.pop() ;
        int ver = t.second , distance = t.first ;
        if (st[ver]) continue ;
        st[ver] = true ;
        for (int i = h[ver] ; i != -1 ; i = ne[i]) {
            int j = e[i] ;
            if (f[j] > distance + w[i]) {
                f[j] = distance + w[i] ;
                heap.push({f[j] , j}) ;
            }
        }
    }
}

signed main () {
    memset(h , -1 , sizeof h) ;
    scanf("%lld%lld%lld%lld" , &maxd , &x , &y , &z) ;
    for (int i = 0 ; i < x ; ++i) {
        add(i , (i + y) % x , y) ;
        add(i , (i + z) % x , z) ;
    }

    dijkstra() ;

    int ans = 0 ;
    for (int i = 0 ; i < maxd ; ++i) {
        if (maxd - f[i] >= 0) {
            ans += (maxd - f[i]) / x + 1 ;
        }
    }

    printf("%lld" , ans) ;

    return 0 ;
}

进死循环了,为什么???

2023/7/1 09:47
加载中...