NC14700 追债之旅 (拆点+最短路)

题目描述
小明现在要追讨一笔债务，已知有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 输出描述:
输出一行，一个整数，代表小明的行程花费和欠债人挥霍的钱的最小总和，如果小明不能抓住欠债人（即不能在第k天及之前到达城n），则输出-1。
示例1
输入

3 3 2
1 3 10
1 2 2
2 3 2
3 7
1
2
3
4
5

输出

13
1

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

3 2 1
1 2 3
2 3 3
10
1
2
3
4

输出

-1
1

说明
小明无法在第1天赶到城3，所以输出-1。
思路：
拆点+dijkstra
将每个点拆为k天时到达的不同情况，跑dijkstra就行了
值得注意的是在入队的时候，由于懒得再写结构体，直接将天数和所在地的标号处理成了一个数。
即：标号+天数*n
这样以后每次从队列头部取出pair的时候，位置就为second%n，天数就为second/n。
代码：

#include
#include
#include
using namespace std;
typedef pair<int,int>PII;
const int N=1005,M=20005;
int dist[N][15];    // dist表示每个点到起点的距离, q 是队列
int h[N], e[M], w[M],ne[M], idx;       // 邻接表
bool st[N][15];     // 存储每个点是否在队列中
int arr[15];
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int n,m,k;
int dijkstra(int s,int t)
{
    memset(dist,0x3f,sizeof dist);
    priority_queue<PII,vector<PII>,greater<PII>>q;
    q.push({0,s+0*n});
    dist[s][0]=0;
    while(!q.empty())
    {
        PII t=q.top();
        q.pop();
        int pos=t.second%n;
        int day=t.second/n;
        int dis=t.first;
        if(st[pos][day])
        {
            continue;
        }
        st[pos][day]=true;
        for(int i=h[pos];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(day+1==k)
            {
                continue;
            }
            if(dist[j][day+1]>dis+w[i]+arr[day])
            {
                dist[j][day+1]=dis+w[i]+arr[day];
                q.push({dist[j][day+1],j+n*(day+1)});
            }
        }
    }
    int res=0x3f3f3f3f;
    for(int i=0;i<k;i++) // 不可能在第k天才到达，否则的话人已经跑路了
    {
        res=min(res,dist[n][i]);
    }
    if(res==0x3f3f3f3f)
    {
        return -1;
    }
    return res;
}
int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m>>k;
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    for(int i=0;i<k;i++)
    {
        cin>>arr[i];
    }
    cout<<dijkstra(1,n);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75