dijkstra 求调
  • 板块P3403 跳楼机
  • 楼主Yorg41
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/20 17:26
  • 上次更新2024/8/20 20:14:25
查看原帖
dijkstra 求调
603391
Yorg41楼主2024/8/20 17:26
#include <bits/stdc++.h>
#define int long long
const int MAXN = 1e6 + 20;
const int MAXM = 1e6 + 20;
const int INF = INT_MAX;

int h;
int x, y, z;

int head[MAXN];
struct edge
{
    int next;
    int to;
    int val;
} Edge[MAXM];
int cnt = 0;

void addedge(int u, int v, int val)
{
    Edge[++cnt].next = head[u];
    Edge[cnt].to = v;
    Edge[cnt].val = val;
    head[u] = cnt;
}

int dis[MAXN];
struct Point
{
    int Num;
    int Val;

    friend bool operator < (const Point &a, const Point &b)
    {
        return a.Val > b.Val;
    }
};
bool vis[MAXN];

void init()
{
    for (int i = 0; i <= x; i++)
    {
        head[i] = -1;
    }
    memset(vis, false, sizeof(vis));
}

void dijkstra()
{
    memset(dis, INF, sizeof(dis));
    dis[0] = 1;
    vis[0] = true;

    std::priority_queue<Point> q;
    q.push((Point){0, 1});

    while(!q.empty())
    {
        Point NowPoint = q.top();
        q.pop();

        if(vis[NowPoint.Num])
            continue;
        vis[NowPoint.Num] = true;

        for (int i = head[NowPoint.Num]; ~i; i = Edge[i].next)
        {
            int Nowto = Edge[i].to;

            if(dis[Nowto] > dis[NowPoint.Num] + Edge[i].val)
            {
                dis[Nowto] = dis[NowPoint.Num] + Edge[i].val;
                q.push((Point){Nowto, dis[Nowto]});
            }
        }
    }
}

signed main()
{
    scanf("%lld", &h);
    scanf("%lld %lld %lld", &x, &y, &z);
    init();
    if(x == 1 && y == 1 && z == 1)
    {
        printf("%lld", h);
    }

    for (int i = 0; i < x; i++)
    {
        addedge(i, (y + i) % x, y);
        addedge(i, (z + i) % x, z);
    }

    dijkstra();

    int Ans = 0;
    for (int i = 0; i < x; i++)
    {
        if(h >= dis[i])
        {
            Ans += (h - dis[i]) / x + 1;
        }
    }

    printf("%lld", Ans);
    return 0;
}
2024/8/20 17:26
加载中...