思路与算法

按互不相同的边权升序处理。状态dp[s][k][v]为从s出发恰用k条已处理边到v的最小和。对边u→v权w按k倒序更新，防止本边重复使用。所有边完成后对k做前缀最小值，回答不超过c条边的查询，c截到n-1。

正确性说明

处理当前边前，状态只使用更小的权，因此追加当前边恰好满足不下降条件；不同边权把它变成严格递增。倒序更新防止在同轮重复。正权路径若含环，删环会降低代价并保持剩余权递增，所以最优简单路径至多n-1边。边数前缀取最小正是至多限制。

复杂度

读入排序O(mlogm)，初始化及边数前缀O(n³)，逐边全起点和边数转移O(mn²)，查询O(q)。空间O(n³+m+q)的宽松上界，查询本身逐条处理不需保存。

易错点

同点查询允许空路径，代价0。路径和不超过149×5000，使用足够大的INF并保持无解不被更新为有限值。不能忽略边数约束只求单源最短路。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, q;
    cin >> n >> m >> q;
    struct E {
        int u, v, w;
    };
    vector<E> e(m);
    for (auto &t : e) {
        cin >> t.u >> t.v >> t.w;
        --t.u;
        --t.v;
    }
    sort(e.begin(), e.end(), [](E a, E b) {
        return a.w < b.w;
    });
    const int INF = 1000000000;
    vector<int> d(n * n * n, INF);
    auto at = [&](int s, int k, int v) -> int & {
        return d[(s * n + k) * n + v];
    };
    for (int s = 0; s < n; s++)
        at(s, 0, s) = 0;
    for (auto t : e)
        for (int s = 0; s < n; s++)
            for (int k = n - 1; k >= 1; k--)
                at(s, k, t.v) = min(at(s, k, t.v), at(s, k - 1, t.u) + t.w);
    for (int s = 0; s < n; s++)
        for (int k = 1; k < n; k++)
            for (int v = 0; v < n; v++)
                at(s, k, v) = min(at(s, k, v), at(s, k - 1, v));
    while (q--) {
        int a, b;
        long long c;
        cin >> a >> b >> c;
        int z = at(a - 1, min<long long>(c, n - 1), b - 1);
        cout << (z == INF ? -1 : z) << '\n';
    }
}