来源：牛客网：

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 65536K，其他语言131072K
64bit IO Format: %lld

文章目录

题目描述

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

输入描述:
第1行输入三个整数n，m，k，代表城市数量，道路数量和指定天数
第2-m+1行，每行输入三个整数u，v，w，代表起点城市，终点城市和支付费用。（数据保证无重边，自环）
第m+2行输入k个整数，第i个整数ai代表第i天欠债人会挥霍的钱。
数据保证：0<n≤1000，0<m≤10000，0<k≤10，1≤u,v≤n，0<w,ai≤1000
输出描述:
输出一行，一个整数，代表小明的行程花费和欠债人挥霍的钱的最小总和，如果小明不能抓住欠债人（即不能在第k天及之前到达城n），则输出-1。
示例1
输入
复制

3 3 2
1 3 10
1 2 2
2 3 2
3 7

输出
复制

13

说明
小明从1-3,总共费用=10（行程）+3（挥霍费用）=13，是方案中最小的（另一条方案花费14）。
示例2
输入
复制

3 2 1
1 2 3
2 3 3
10

输出
复制

-1

说明
小明无法在第1天赶到城3，所以输出-1。

题解：

最短路问题
就是求最短路，并根据是第几天加上相应的数
松弛条件改为dis[d+1][v]>dis[d][u]+w+a[d+1]
dis[x][y]：x表示第x天，y为点
a[]：a存储的第x天的挥霍费用
记得特判能否在d天内抓住嫌疑犯

代码：

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f;

struct node{
   
    int d,u,w;
    bool operator< (const node &p)const{
   
        return w>p.w;
    }
};
int n,m,k;
vector<pii> g[maxn];
int dis[1010][1010],a[maxn];
void dij(){
   
    memset(dis,inf,sizeof dis);
    dis[0][1]=0;
    priority_queue<node>q;
    q.push((node){
   0,1,0});
    while(!q.empty()){
   
        node p=q.top();
        q.pop();
        int u=p.u,d=p.d;
        if(p.w>dis[d][u])continue;
        for(auto i:g[u]){
   
            int v=i.fi,w=i.se;
            if(d+1<=k&&dis[d+1][v]>dis[d][u]+w+a[d+1]){
   
                dis[d+1][v]=dis[d][u]+w+a[d+1];
                q.push((node){
   d+1,v,dis[d+1][v]});
            }
        }
    }
}
int main()
{
   
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
   
        int u,v,w;
        cin>>u>>v>>w;
        g[u].pb(mp(v,w));
        g[v].pb(mp(u,w));
    }
    for(int i=1;i<=k;i++)cin>>a[i];
    dij();
    int ans=inf;
    for(int i=1;i<=k;i++)
        ans=min(ans,dis[i][n]);
    if(ans!=inf)cout<<ans;
    else cout<<-1;
    return 0;
}