x

bh2013 · 2025-10-04 14:06:24 · 个人记录

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n, m, t, c[85], dp[85][85], w[85][85][85], nxt[85][85];
vector <int> to[85];
// dp[i][j] 表示在第 i 天到达第 j 个城市的最小花费 

void init() {
    memset(dp, 0x3f, sizeof(dp));
    dp[0][1] = 0;
    memset(nxt, 0, sizeof(nxt));
    for (int i = 1; i <= n; i ++) to[i].clear();
    return ;
}
void solve() {
    cin >> n >> m >> t;
    init();
    for (int i = 1, x, y; i <= m; i ++) {
        cin >> x >> y;
        for (int j = 1; j <= t; j ++) cin >> w[x][y][j];
        for (int j = 1; j <= t; j ++) w[y][x][j] = w[x][y][j];
        to[x].emplace_back(y), to[y].emplace_back(x);
    }
    for (int i = 1; i <= n; i ++) cin >> c[i];
    for (int i = 1; i <= t; i ++) {
        for (int j = 1; j <= n; j ++) {
            for (int k : to[j]) {
                if (nxt[i - 1][k] != j) {
                    if (dp[i][j] > dp[i - 1][k] + w[k][j][i]) dp[i][j] = dp[i - 1][k] + w[k][j][i], nxt[i][j] = k;
                    else if (dp[i][j] == dp[i - 1][k] + w[k][j][i]) nxt[i][j] = -1;
                } else {
                    if (dp[i][j] > dp[i - 1][k] + w[k][j][i] + c[k]) dp[i][j] = dp[i - 1][k] + w[k][j][i] + c[k], nxt[i][j] = k;
                    else if (dp[i][j] == dp[i - 1][k] + w[k][j][i] + c[k]) nxt[i][j] = -1;
                }
            }
        }
    }
    int ans = 0x3f3f3f3f3f3f3f3f;
    for (int i = 1; i <= n; i ++) ans = min(ans, dp[t][i]);
    cout << ans << '\n';
    return ;
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//  freopen("aviation.in", "r", stdin);
//  freopen("aviation.out", "w", stdout);
    int T;
    cin >> T;
    while (T --) solve();
    return 0;
}