追债之旅

1
输出一行，一个整数，代表小明的行程花费和欠债人挥霍的钱的最小总和，如果小明不能抓住欠债人（即不能在第k天及之前到达城n），则输出-1。

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

1
13

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

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

1
-1

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

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
76
77
78
79
80
81
82
83
84
85
86
#include<iostream>
#include<algorithm>
#include<set>
#include<vector>
#include<cstring>
#include<queue>
#define ll long long
 
using namespace std;
 
const int N = 10000+10;
 
int idx,h[N],e[N*2],ne[N*2],w[N*2];
int n,m,k;
int cost[N];
int dis[1010][20];
int ans = 0x3f3f3f3f;

void add(int a, int b, int c)
{
	e[idx] = b;
	w[idx] = c;
	ne[idx] = h[a];
	h[a] = idx++;
}
 
struct node{
	int u,len,step;
	bool operator < (const node &tem)const
	{
		return len < tem.len;
	}
};
 
void dij()
{
	
	dis[1][0] = 0;
	priority_queue<node> q;
	q.push({1,0,0});
	
	while(q.size())
	{
		node a = q.top();
		q.pop();
		
		int u = a.u;
		int len = a.len;
		int step = a.step;
		
		if(step >= k || u == n || len > dis[u][step]) continue;
		
		for(int i=h[u]; i!=-1; i=ne[i])
		{
			int v = e[i];
			int ww = w[i];
			if(dis[v][step+1] > dis[u][step] + ww + cost[step+1])
			{
				dis[v][step+1] = dis[u][step] + ww + cost[step+1];
				q.push({v, dis[v][step+1], step+1});
			}				
		}
	}
	for(int i=1; i<=k; i++) ans = min(ans, dis[n][i]);
}
 
int main()
{
	memset(dis, 0x3f, sizeof dis);
	memset(h, -1, sizeof h);
	cin>>n>>m>>k;
	while(m--)
	{
		int a,b,c;
		cin>>a>>b>>c;
		add(a,b,c);
		add(b,a,c);
	}
	for(int i=1; i<=k; i++) cin>>cost[i];
	
	dij();
	
	if(ans == 0x3f3f3f3f) puts("-1");
	else cout<<ans;
	return 0;
}