松弛操作，循环dp

题意：

分析：

又是这种题，很好，对于已经明白松弛操作与循环dp的我来说已经不成问题了。
给出dp状态dp[i][j] 指在第j步到达节点i的最短路径
d[i][j] = min(d[k][j-1] + edge(i,k) + cost[j] k为i相邻节点)
这是个无限递归的循环dp
关于循环dp https://blog.nowcoder.net/n/8316b13c345d49b08b2ae7f41c49da71
##代码如下:

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<functional>
using namespace std;
typedef pair<int, int> pii;
typedef pair<int, pii> pip;
struct edge { int to, cost; };
const int max_n = 1e3 + 100;
const int inf = 2e9;
int d[max_n][15];
vector<edge> G[max_n];
int n, m, k;
int cost[15];


void dijstra(int s,int t) {
    for (int i = 1;i <= n;i++)
        for (int j = 0;j <= k;j++)
            d[i][j] = inf;
    priority_queue<pip, vector<pip>, greater<pip>> que;
    d[s][t] = 0;que.push({ d[s][t],{s,t} });
    while (!que.empty()) {
        pip p = que.top();que.pop();
        pii pos = p.second;int dist = p.first;
        if (dist > d[pos.first][pos.second])continue;
        d[pos.first][pos.second] = dist;
        if (pos.second == k)continue;
        for (int i = 0;i < G[pos.first].size();i++) {
            edge& e = G[pos.first][i];
            if (d[e.to][pos.second + 1] < dist + e.cost + cost[pos.second + 1])continue;
            d[e.to][pos.second + 1] = dist + e.cost + cost[pos.second + 1];
            que.push({ d[e.to][pos.second + 1],{e.to,pos.second + 1} });
        }
    }
}


int main() {
    ios::sync_with_stdio(0);
    cin >> n >> m >> k;
    for (int i = 1;i <= m;i++) {
        int u, v, w;cin >> u >> v >> w;
        G[u].push_back({ v,w });
        G[v].push_back({ u,w });
    }
    for (int i = 1;i <= k;i++)cin >> cost[i];
    dijstra(1, 0);
    int ans = inf;
    for (int i = 0;i <= k;i++)
        ans = min(d[n][i], ans);
    if (ans == inf)cout << -1 << endl;
    else cout << ans << endl;
}