题解 | #Rinne Loves Graph#

//迪杰斯特拉算法配合上动态规划
//动态规划的数组为：dp[i][j]。表示到达第i号城镇，穿过了k次所走的最短路
//一定要注意迪杰斯特拉将优先队列里面已经作为最短判断过了不要再判断了。否则会发生很奇怪的错误。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxnn = 4000*2+10;
const int maxn = 800+10;
//使用链式前向星存图
struct sy{
    int to;
    int val;
    int next;
}edge[maxnn];
struct Node{
    int number;
    int val;
    int k;
    bool operator < (const Node &n) const
    {
        return val>n.val;
    }
};
int head[maxnn];
priority_queue<Node> pq;
int dp[maxn][maxn];
bool fl[maxn];
int n, m, k;
int cnt = 0;
bool st[maxn][maxn];
void add_edge(int u, int v, int w)
{
    edge[++cnt].next = head[u];
    edge[cnt].to = v;
    edge[cnt].val = w;
    head[u] = cnt;
}

void Dijkstra()
{
    memset(dp, 127, sizeof(dp));
    dp[1][0] = 0;
    pq.push({1, 0, 0});
    while (pq.size())
    {
        int number = pq.top().number;
        int val = pq.top().val;
        int K = pq.top().k;
        pq.pop();
        if (K>k||st[number][K]) continue;
        st[number][k] = true;
        for (int i=head[number];i;i = edge[i].next)
        {
            int next = edge[i].to;
            int eval = edge[i].val;
//             cout<<"eval="<<eval<<endl;
            if (fl[number]==1)
            {
                if (dp[number][K]+eval<dp[next][K+1])
                {
                    dp[next][K+1] = dp[number][K]+eval;
                    pq.push({next, dp[next][K+1], K+1});
                }
            } else {
                if (dp[number][K]+eval<dp[next][K])
                {
                    dp[next][K] = dp[number][K]+eval;
                    pq.push({next, dp[next][K], K});
                }
            }
        }
    }
    int ans = INT_MAX;
    for (int i=0;i<=k;i++) 
    {
        ans = min(ans, dp[n][i]);
//         cout<<dp[n][i]<<endl;
    }
    if (ans==INT_MAX) 
        cout<<-1<<endl;
    else cout<<ans<<endl;
}

signed main()
{
    int u, v, w;
    cin>>n>>m>>k;
    for (int i=1;i<=n;i++) cin>>fl[i];
    for (int i=1;i<=m;i++)
    {
        cin>>u>>v>>w;
        add_edge(u, v, w);
        add_edge(v, u, w);
    }
    Dijkstra();
    return 0;
}