dp松弛问题(循环特性)

题意：

分析：

dp松弛问题。这是我的总结。
所谓的最短路，不过是dp只不过该dp无法借由循环和记忆化搜索实现(因为有环使其左右横跳)
详细见我的另一篇题解，正好是题单中的下一题：https://blog.nowcoder.net/n/8316b13c345d49b08b2ae7f41c49da71
我们在这里使用dp：dp[i][j]表示在穿过了j次***城市后i节点到达节点1的最短路径。
那么初始状态dp[1][0] = 0
状态转移方程：
dp[i][j] = min( min(d[k][j] , k为与i相邻的非***城市) ， min(d[k][j-1] , k为与i相邻的***城市) )
当j == 0时 dp[i] = min(d[k][j] , k为与i相邻的非***城市)

我们很容易就发现这实际上是个循环dp问题！！！我们的状态会在两个非***城市间左右横跳
对待循环dp我们依据边的条件使用Bellman-Ford系列算法，这里使用Dijstra算法。

代码如下：

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<functional>
using namespace std;
typedef pair<int, int> pii;
typedef pair<int, pii> ppos;
struct edge { int to, cost; bool locked; };
const int max_n = 1000;
const int inf = 2e9;
int n, k, m;
bool node[max_n];
vector<edge> G[max_n];
int d[max_n][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<ppos, vector<ppos>, greater<ppos>> que;
    d[s][t] = 0;que.push({ d[s][t],{s,t} });
    while (!que.empty()) {
        ppos p = que.top();que.pop();
        pii pos = p.second;int dist = p.first;
        if (d[pos.first][pos.second] < dist)continue;
        d[pos.first][pos.second] = dist;
        if (pos.second == k && node[pos.first])continue;
        for (int i = 0;i < G[pos.first].size();i++) {
            edge e = G[pos.first][i];
            if (d[e.to][e.locked + pos.second] > dist + e.cost) {
                d[e.to][e.locked + pos.second] = dist + e.cost;
                que.push({ d[e.to][e.locked + pos.second],{e.to,e.locked + pos.second} });
            }
        }
    }
}

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