题目传送门:后山OJ P110721

Description

有一张 $n$ 个点 $m$ 条边的有向图,每条边有一个互不相同的边权 $w$ ,有 $q$ 个询问,要求你从点 $a$ 经过不超过 $c$ 条边到点 $b$ ,要求经过的边权不下降且和尽量小,求出满足条件的最小的边权和,如果没有合法方案则输出 $−1$ 。

Solution

设 $f[i][j][k]$ 表示从 $i$ 到 $j$ 正好经过 $k$ 条边,且满足条件的最小边权和。

用类似Floyd的方法更新每一条边(从 $f[i][x][k]$ 到 $f[i][y][k+1]$ )。

然后求一遍前缀最小值。就可以 $O(1)$ 查询了。

$O(n^3+n^2m)$

Code

/*
 * @Name: 110721
 * @Author: Lovely_XianShen
 * @Date: 2019-10-29 15:37:26
 * @Aqours!Sunshine!!
 */
#include<bits/stdc++.h>
using namespace std;

inline int read() {
    int a = 0; char x = getchar();
    while (x < '0' || x > '9')x = getchar();
    while (x >= '0' && x <= '9')a = (a << 3) + (a << 1) + x - 48, x = getchar();
    return a;
}

int f[155][155][155], n, m, q;

struct point {
    int x, y, v;
    bool operator < (const point &a) const {
        return v < a.v;
    }
} p[5005];

int main() {
    memset(f, 0x3f, sizeof f);
    n = read();
    m = read();
    q = read();
    for (int i = 1; i <= m; i++) {
        p[i].x = read();
        p[i].y = read();
        p[i].v = read();
    }
    sort(p + 1, p + m + 1);
    for (int i = 1; i <= n; i++)
        f[i][i][0] = 0;
    for (int k = 1; k <= m; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 0; j <= n; j++)
                f[i][p[k].y][j + 1] = min(f[i][p[k].y][j + 1], f[i][p[k].x][j] + p[k].v);
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                f[i][j][k] = min(f[i][j][k], f[i][j][k - 1]);
    while (q--) {
        int x = read(), y = read(), z = read();
        z = min(z, n);
        if (f[x][y][z] == 0x3f3f3f3f)
            puts("-1");
        else
            cout << f[x][y][z] << endl;
    }
    return 0;
}