每如一题 8月6日追债之旅 多维最短路

题目链接：https://ac.nowcoder.com/acm/problem/14700
题目大意：

思路”：我们用dis[u][i]：表示第i天到达u的最大费用。

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

struct Edge{
    int to, w, nxt;
}e[30005];
int head[30005], cut=0;

struct ZDL{
    int dis[1005][15], vis[1005][15];
    struct Node{
        int to, T, w;
        bool operator<(const Node &a) const {
            return w>a.w;
        }
    };
    priority_queue<Node> q;
    void init(){
        cut=0;
        memset(dis, 0x3f, sizeof(dis));
        memset(head, 0, sizeof(head));
        memset(vis, 0, sizeof(vis));
    }
    void addedge(int u, int v, int w){
        e[++cut]={v, w, head[u]};
        head[u]=cut;
    }
    void getans(int s){
        q.push({s, 0, 0}); dis[s][0]=0;
        while(!q.empty()){
            Node now=q.top(); q.pop();
            int u=now.to, T=now.T;
            if(T>10||vis[u][T]) continue;
            vis[u][T]=1;
            for(int i=head[u]; i; i=e[i].nxt){
                int x=e[i].to;
                if(dis[x][T+1]>dis[u][T]+e[i].w&&!vis[x][T+1]){
                    dis[x][T+1]=dis[u][T]+e[i].w;
                    q.push({x, T+1, dis[x][T+1]});
                }
            }
        }
    }

}T;

int a[15];
int main() {

    int n, m , k; scanf("%d%d%d", &n, &m, &k);
    int x, y, w;
    T.init();
    for(int i=1; i<=m; i++){
        scanf("%d%d%d", &x, &y, &w);
        T.addedge(x, y, w);
        T.addedge(y, x, w);
    }
    for(int i=1; i<=k; i++){
        scanf("%d", &a[i]);
        a[i]+=a[i-1];
    }
    T.getans(1);
    int mx=1<<30;
    for(int i=0; i<=k; i++){
        if(T.dis[n][i]!=T.dis[n+1][0]){
            mx=min(mx, T.dis[n][i]+a[i]);
        }
    }
    if(mx==(1<<30)){
        printf("-1\n");
    }
    else{
        printf("%d\n", mx);
    }

    return 0;

}