追债之旅

分析

简简单单最短路。

只是要记录一下走了几天罢了，定义为从 1 到 i 走了 j 天的行程花费和欠债人挥霍的钱的最小总和。

。

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
const int inf = 0x3f3f3f3f;
const int maxn = 1110;
const int M = 1e9+7;
int n,m,k;

int a[maxn],dp[maxn][20];       //从1到i走了j天

vector<pii> v[maxn];

bool vis[maxn];

void spfa(int u)
{
    mem(dp,inf);dp[u][0] = 0;
    queue<int> q;q.push(u);
    while(q.size())
    {
        u = q.front();q.pop();vis[u] = 0;
        for(auto i : v[u])
        {
            for(int j = 0; j < k; j++)        //枚举走了几天
            {
                if(dp[i.first][j+1] > dp[u][j] + a[j+1] + i.second)
                {
                    dp[i.first][j+1] = dp[u][j] + a[j+1] + i.second;
                    if(vis[i.first]) continue;
                    vis[i.first] = 1;
                    q.push(i.first);
                }
            }
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>n>>m>>k;
    for(int i = 1,x,y,z; i <= m; i++) 
    {
        cin>>x>>y>>z;
        v[x].push_back({y,z});
        v[y].push_back({x,z});
    }
    for(int i = 1; i <= k; i++) cin>>a[i];
    spfa(1);
    int ans = inf;  
    for(int i = 1; i <= k; i++) ans = min(ans,dp[n][i]);
    if(ans == inf) ans = -1;
    cout<<ans<<endl;
    return 0;
}