AT_abc340_d 题解

yyrwlj · 2024-02-11 12:46:20 · 题解

思路

考虑将原问题转化成图论问题。

对于形如花费 c 时间通过第 a 关达到第 b 关这样的关系，就相当于 a 到 b 连一条边权为 c 的边。

然后跑一遍堆优化 dijkstra 求点 1 到 n 的最短路即可。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
typedef long long LL;
typedef pair<LL, int> PII;
struct Edge{
    int e, to, nxt;
}g[N << 1];
int h[N], idx;
LL dis[N];
bool st[N];
void add(int a,int b,int c)
{
    g[++idx] = {c, b, h[a]}, h[a] = idx;
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i=1;i<=n;i++)
    {
        int a, b, x;
        scanf("%d%d%d", &a, &b, &x);
        add(i, i + 1, a);
        add(i, x, b);
    }
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII> > q;
    q.push({0, 1});
    while (!q.empty())
    {
        PII now = q.top();
        q.pop();
        int u = now.second;
        LL d = now.first;
        if (st[u])
            continue;
        st[u] = true;
        for (int i = h[u]; i; i = g[i].nxt)
        {
            int j = g[i].to, w = g[i].e;
            if (dis[j] > d + w)
            {
                dis[j] = d + w;
                q.push({dis[j], j});
            }
        }
    }
    printf("%lld", dis[n]);
    return 0;
}