追债之旅

题目描述

小明现在要追讨一笔债务，已知有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。

题解

分层图经典题

分层图最短路是指在可以进行分层图的图上解决最短路问题。分层图：可以理解为有多个平行的图。

一般模型是：在一个正常的图上可以进行 k 次决策，对于每次决策，不影响图的结构，只影响目前的状态或代价。一般将决策前的状态和决策后的状态之间连接一条权值为决策代价的边，表示付出该代价后就可以转换状态了。

对于此问题有两种方法解决

1.建图时直接建成k+1层。
2.在跑最短路的时候多开一维记录信息。

像本题，可以直接用表示第i次经过的是j的最短路，跑的时候多记录一维的信息就可以了。或者建成如下的k+1层图跑最短路即可。

代码

#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
#define pii pair<int,int>
#define all(A) A.begin(), A.end()
#define fi first
#define se second
#define MP make_pair
#define rep(i,n) for(register int i=0;i<(n);++i)
#define repi(i,a,b) for(register int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(register int i=int(b);i>=(a);--i)
template<typename T>
inline T read(){
    T s=0,f=1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f=-1;ch = getchar();}
    while(isdigit(ch)) {s=(s<<3)+(s<<1)+ch-48;ch = getchar();}
    return s*f;
}
#define gn() read<int>()
#define gl() read<ll>()
template<typename T>
inline void print(T x) {
    if(x<0) putchar('-'), x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
////////////////////////////////////////////////////////////////////////
const int N=2e5+100;
const int mod=1e9+7;
int n,m,k;
vector<pii> v[10050];
int dis[15][1050],a[15];
void dij(){
    dis[0][1]=0;
    priority_queue<pair<int,pii> >q;
    q.push(MP(0,MP(1,0)));
    while(!q.empty()){
        pii now=q.top().se;
        q.pop();
        if(now.se+1>k)continue;
        for(auto k:v[now.fi]){
            if(dis[now.se+1][k.fi]>dis[now.se][now.fi]+k.se+a[now.se+1]){
                dis[now.se+1][k.fi]=dis[now.se][now.fi]+k.se+a[now.se+1];
                q.push(MP(-dis[now.se+1][k.fi],MP(k.fi,now.se+1)));
            }
        }
    }
}
void solve(){
    n=gn(),m=gn();k=gn();
    memset(dis,0x3f,sizeof(dis));
    repi(i,1,n)v[i].clear();
    repi(i,1,m){
        int x=gn(),y=gn(),w=gn();
        v[x].pb(MP(y,w));
        v[y].pb(MP(x,w));
    }
    repi(i,1,k)a[i]=gn();
    dij();
    int ans=0x3f3f3f3f;
    repi(i,1,k)ans=min(ans,dis[i][n]);
    if(ans==0x3f3f3f3f)ans=-1;
    print(ans),putchar(10);
}
////////////////////////////////////////////////////////////////////////
int main(){
    solve();
}
/**
* In every life we have some trouble
* When you worry you make it double
* Don't worry,be happy.
**/