题目大意

给定一张无向图，每条边有费用，每走 条边会有额外费用 ，至多走 条边。问从点 到点 的最小费用路。

题解

把每一个点拆成 个点，相当于对点记录一下时间即可直接套用 Dijkstra 算法。

#include <bits/stdc++.h>
#define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp)
#define REPR(temp, init_val, end_val) for (int temp = init_val; temp >= end_val; --temp)
#define fst first
#define snd second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> intpair;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, m, k;
priority_queue<pair<int, intpair > > pq;
int dis[1005][12];
int to[20005], nxt[20005], w[20005], at[1005] = {0}, cnt = 0;
int c[12];
void init(){
    n = read(), m = read(), k = read();
    REP(i, 1, m){
        int u = read(), v = read(), ww = read();
        to[++cnt] = v, nxt[cnt] = at[u], w[cnt] = ww, at[u] = cnt;
        to[++cnt] = u, nxt[cnt] = at[v], w[cnt] = ww, at[v] = cnt;
    }
    REP(i, 1, k){
        c[i] = read();
    }
}
void solve(){
    memset(dis, 0x3f, sizeof(dis));
    dis[1][0] = 0;
    pq.push(make_pair(0, make_pair(1, 0)));
    for (; ; ){
        while (!pq.empty()){
            if (-pq.top().fst > dis[pq.top().snd.fst][pq.top().snd.snd])
                pq.pop();
            else break;
        }
        if (pq.empty()) break;
        int d = -pq.top().fst;
        int p = pq.top().snd.fst;
        int tm = pq.top().snd.snd;
        pq.pop();
        if (tm == k) continue;
        for (int i = at[p]; i; i = nxt[i]){
            if (d + w[i] + c[tm + 1] < dis[to[i]][tm + 1])
                dis[to[i]][tm + 1] = d + w[i] + c[tm + 1], 
                pq.push(make_pair(-dis[to[i]][tm + 1], make_pair(to[i], tm + 1)));
        }
    }
    int ans = 0x3f3f3f3f;
    REP(i, 0, k) ans = min(ans, dis[n][i]);
    printf("%d\n", ans == 0x3f3f3f3f ? -1: ans);
}
int main(){
    init();
    solve();
    return 0;
}