[数据结构与算法]牛客《追债之旅》NC14700

题目链接：登录—专业IT笔试面试备考平台_牛客网??????

题目简述：

你需要在k天内赶往n号点，否则你的借你的钱的人就会跑路了，并且你每在路上花费一天，你的钱就会被别人挥霍，并且每天的挥霍数额不等，你通过一条边的时间为一天，并且有相应的费用。你需要算出你在赶往n号点之后你的花费加上他挥霍的钱的最小值。

首先我们不难发现，题目的K很小只有10，因此我们可以利用这个k来算出在第k天到达n号点的最小路费。那么我们在进行最短路转移的时候就多记录一下天就可以了

code：

#include <bits/stdc++.h>
using namespace std;
struct node {
    int f,t,val,nex;
}rt[10000010];
int head[1000010];
int cnt;
int ans[1000010][15];
void add(int x,int y,int z) {
    rt[++ cnt].f = x;
    rt[cnt].t = y;
    rt[cnt].val = z;
    rt[cnt].nex = head[x];
    head[x] = cnt;
}
int a,b,c;
int x,y,z;
int qian[10000010];
int main() {
    cin>>a>>b>>c;
    priority_queue<pair<int ,pair<int ,int > > > p;
    memset(ans,0x3f,sizeof ans);
    ans[1][0] = 0;
    for(int i = 1;i <= b;i ++) {
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
    p.push(make_pair(0, make_pair(1,0)));
    while (!p.empty()) {
        int qaq = p.top().second.first;
        int ty = p.top().second.second;
        p.pop();
        for(int i = head[qaq];i;i = rt[i].nex) {
            if(ans[rt[i].t][ty + 1] > ans[qaq][ty] + rt[i].val && ty + 1 <= c) {
                ans[rt[i].t][ty + 1] = ans[qaq][ty] + rt[i].val;
                p.push(make_pair(-ans[rt[i].t][ty + 1], make_pair(rt[i].t,ty + 1)));
            }
        }
    }
    for(int i = 1;i <= c;i ++) {
        scanf("%d",&x);
        qian[i] = qian[i - 1] + x;
    }
    int ans1 = 0x3f3f3f3f;
    for(int i = 1;i <= c;i ++) {
        ans1 = min(ans1,ans[a][i] + qian[i]);
    }
    if(ans1 != 0x3f3f3f3f)
        cout<<ans1;
    else
        cout<<-1;
    return 0;
}