【每日一题】追债之旅

题目

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

解题思路

使用 BFS 算法。

表示与编号为 的城市连接的城市。

表示从城市 到城市 这条道路中需要支付的费用。

表示第 天欠债人挥霍的钱。

表示第 天到达城市 时的最小花费。在 函数中，实时更新最小花费。当天数大于 时，就不再计算。

最后，遍历从 1 到 天的 ，取最小值。

C++代码

#include<iostream>
#include<vector>
#include<queue>
#include<map>
using namespace std;

const int inf = 0x3f3f3f3f;
vector<vector<int>> edges;
map<pair<int,int>, int> mp;
vector<int> a;
vector<vector<int>> cost;

void bfs(int start, int k){
    queue<int> que, que2, que3;
    que.push(start);
    int day = 1;
    while(!que.empty()){
        int x = que.front();
        que.pop();
        for(int i=0; i<edges[x].size(); ++i){
            int y = edges[x][i];
            int tmp = cost[day-1][x] + mp[make_pair(x,y)] + a[day];
            if(cost[day][y] > tmp){
                cost[day][y] = tmp;
                que2.push(y);
            }
        }
        if(que.empty()){
            ++day;
            que = que2;
            que2 = que3;
        }
        if(day>k)
            return;
    }
}

int main(){
    int n, m, k;
    cin >> n >> m >> k;
    if(n==1){
        cout << 0 << endl;
        return 0;
    }
    edges.resize(n+1);
    int u, v, w;
    for(int i=0; i<m; ++i){
        cin >> u >> v >> w;
        edges[u].push_back(v);
        edges[v].push_back(u);
        mp[make_pair(u,v)] = w;
        mp[make_pair(v,u)] = w;
    }
    a.resize(n+1);
    for(int i=1; i<=n; ++i)
        cin >> a[i];

    cost.resize(k+1, vector<int>(n+1, inf));
    cost[0][1] = 0;
    bfs(1,k);

    int ans = inf;
    for(int i=1; i<=k; ++i){
        ans = min(ans, cost[i][n]);
    }
    if(ans == inf)
        cout << -1 << endl;
    else
        cout << ans << endl;
    return 0;
}