Description

小明现在要追讨一笔债务，已知有n座城市，每个城市都有编号，城市与城市之间存在道路相连（每条道路都是双向的），经过任意一条道路需要支付费用。小明一开始位于编号为1的城市，欠债人位于编号为n的城市。小明每次从一个城市到达另一个城市需要耗时1天，而欠债人每天都会挥霍一定的钱，等到第k天后（即第k+1天）他就会离开城n并再也找不到了。小明必须要在他离开前抓到他（最开始为第0天），同时希望自己的行程花费和欠债人挥霍的钱的总和最小，你能帮他计算一下最小总和吗？

Solution

显然是最短路问题，求1到n的最短路，由于多出了个欠债人的影响，考虑分层图最短路，用 代表第 天到达 城市的最短路径，那么剩下的问题就可以用 去解决了，后一天的状态能从当前天转移过来。
WA了很多次，没想到当成n条边输入了0.0

Code

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5 + 5;
const int mod = 1e9 + 7;
int a[N], dist[N][11], n, m, k;
bool vis[N][11];
struct qnode {
    int v, cost, day;
    bool operator < (const qnode &r)const{
      return cost > r.cost;
  }
    qnode(int _v = 0, int _cost = 0, int _day = 0): v(_v), cost(_cost), day(_day){}
};
struct Edge {
    int v, cost;
    Edge(int _v = 0, int _cost = 0): v(_v), cost(_cost){}
};
vector<Edge> G[N];
void Dijkstra(int n, int start) {
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= 10; j++) {
            dist[i][j] = 1e9;
            vis[i][j] = false;
        }
    }
    priority_queue<qnode> q;
    dist[start][0] = 0;
    q.push(qnode(start, 0, 0));
    while(!q.empty()) {
        qnode tmp = q.top(); q.pop();
        int u = tmp.v;
        int day = tmp.day;
        if(vis[u][day]) continue;
        vis[u][day] = true;
        for(int i = 0; i < G[u].size(); i++) {
            int v = G[u][i].v;
            int cost = G[u][i].cost;
            int j = day + 1;
            if(j > k) continue;
            if(!vis[v][j] && dist[v][j] > dist[u][j - 1] + cost + a[j]) {
                dist[v][j] = dist[u][j - 1] + cost + a[j];
                q.push(qnode(v, dist[v][j], j));
            } 
        }
    }
} 
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> m >> k;
    for(int i = 1; i <= m; i++) {
        int x, y, z; cin >> x >> y >> z; 
        G[x].push_back({y, z}), G[y].push_back({x, z});
    }
    for(int i = 1; i <= k; i++) cin >> a[i];
    Dijkstra(n, 1);
    int ans = 1e9;
    for(int i = 0; i <= k; i++) {
        ans = min(ans, dist[n][i]);
    }
    if(ans != 1e9)
        cout << ans << "\n";
    else cout << -1 << "\n";
    return 0;
}