追债之旅

题意：
有n个城市，小明再1号城市，它的欠债人在n号城市，城市之间有道路连接，不过需要交路费，而且欠债人每天都会花费一些钱，每天你只能走一条道路从一个城市到另一个城市，求你最少的花费（路费+欠债人花费）为多少？

思路：
最短路的变形题，多了个欠债人每天的花费。
用val[i][j]表示第i天在第j个城市的最少花费。
松弛操作条件为：val[t+1][to]>cost+a[t+1]+val[t][v]（t<k）;

代码：

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const ll inf=1000000007;

struct w
{
    int to, cost;
} w;

struct p
{
    int v, val, day;
} p;

vector<struct w>g[10005];

int val[15][1005];

int n, k, a[105], ans=inf;

int dij()
{
    fill(val[0],val[0]+15*1005,inf);
    p.v=1;
    p.val=0;
    p.day=0;
    val[0][1]=0;
    queue<struct p> q;
    q.push(p);
    while(!q.empty())
    {
        p=q.front();
        q.pop();
        if(p.val>val[p.day][p.v])
            continue;
        int v=p.v, t=p.day, va=p.val;
        if(t<=k&&v==n)
        {
            ans=min(ans,va);
        }
        for(int i=0; i<g[v].size(); i++)
        {
            int to=g[v][i].to, cost=g[v][i].cost;
            if(t<k&&val[t+1][to]>cost+a[t+1]+val[t][v])
            {
                val[t+1][to]=cost+a[t+1]+val[t][v];
                p.v=to;
                p.val=val[t+1][to];
                p.day=t+1;
                q.push(p);
            }
        }
    }
    if(ans==inf)
        return -1;
    else
        return ans;
}

int main()
{
    int m;
    scanf("%d %d %d",&n,&m,&k);
    for(int i=0; i<m; i++)
    {
        int u, v;
        scanf("%d%d%d",&u,&v,&w.cost);
        w.to=v;
        g[u].push_back(w);
        w.to=u;
        g[v].push_back(w);
    }
    for(int i=1; i<=k; i++)
    {
        scanf("%d",&a[i]);
    }
    cout << dij() << endl;
    return 0;
}