P9504 『MGOI』Simple Round I | C. 魔法禁林

信息向阳花木 · 2023-08-06 21:23:17 · 题解

（这是一篇已经过了的题解，改动了一下代码）

赛时第一眼看，是个无向图，求一个点到另外一个点的最小值，诶，这不裸的最短路嘛，然后兴高采烈地倒着跑了个 dijkstra，喜提 30 分。仔细一看，w \le 100，发现当 k > 100 时，生命就是永恒的，于是加了个剪枝，就过啦。

具体地，正常的最短路量有一个，本题有两个。于是我们定义 dist_{i,j} 表示当前魔力值为 i 走到 j 的最小生命值。每倒着走一条边，k 就多了 1。当 k > 100 时，往后无论怎么走，生命值都不会减少，k 就不用加了，直接跳过这个状态即可。其他和裸最短路没啥区别。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

#define PII pair<int, pair<int, int> >
#define x first
#define y second

const int N = 20010, M = 80010;

inline void in(int &x)
{
    x = 0; bool f = 0; char c = getchar();
    while(c < '0' || c > '9')
    {
        if(c == '-') f = 1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')
    {
        x = (x << 3) + (x << 1) + (c & 15);
        c = getchar();
    }
    x = f ? -x : x;
}

inline void out(int x)
{
    if(x < 0) putchar('-'), x = -x;
    if(x / 10) out(x / 10);
    putchar((x % 10) | 48);
}

int n, m, s, t, ans = 0x3f3f3f3f;
int h[N], e[M], ne[M], w[M], idx;
int dist[210][N], res[N];
bool st[210][N];
priority_queue<PII, vector<PII>, greater<PII> > q;

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

void dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[0][s] =0;
    q.push({0, {0, s}});

    while (!q.empty())
    {
        PII p = q.top();
        q.pop();

        int id = p.second.second, k = p.second.first;
        //对于一个  PII，first 表示最小生命值，second.first 表示当前魔法值，second.second 表示当前结点编号 
        if(st[k][id]) continue;
        st[k][id] = 1;

        if(k > 100) { ans = p.first; continue; } //剪枝，注意这里要记录一下答案（改动的地方，不然会被 hack）

        for (int i = h[id]; ~i; i = ne[i])
        {
            int j = e[i];
            if(dist[k + 1][j] > dist[k][id] + w[i] / (k + 1))
            {
                dist[k + 1][j] = dist[k][id] + w[i] / (k + 1);
                q.push({dist[k + 1][j], {k + 1, j}});
            } //更新状态 
        }
    }
    return;
}

int main()
{
    memset(h, -1, sizeof h);

    in(n); in(m); in(t); in(s); //倒着做 
    while (m -- )
    {
        int x, y, z;
        in(x); in(y); in(z);
        add(x, y, z); add(y, x, z);
    }

    dijkstra();

    for(int i = 0; i <= 101; i ++ ) ans = min(ans, dist[i][t]);
    printf("%d\n", ans);

    return 0;
}