追债之旅 Dijstra变形

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof a)
#define N 1009
#define M 20009
int h[N];
int e[M],ne[M],idx,a[20],w[M]; 
ll  dist[20][N];//dist[i][j]表示第i天到大j号点的最小花费 
int vis[20][N];
int n,m,k;
//天数，点的位置，花费 
struct node
{
   
	ll day,p,val; 
	//改变堆里面的排序规则，使得按照w从小到大排序 
	bool operator < (const node &t) const 
	{
   
		return val>t.val;
	}
};
ll Read()
{
   
	char ch;
	ll s=0,w=1;
	ch = getchar();
	while(ch<'0'||ch>'9'){
   if(ch=='-') w = -1; ch = getchar();}
	while(ch>='0'&&ch<='9'){
    s = s*10 +ch-'0'; ch = getchar(); }
	return s*w;
}
void add(int x,int y,int z)
{
   
	e[idx] = y;
	w[idx] = z;
	ne[idx] = h[x];
	h[x] = idx++;
}
void Dijstra()
{
   
	mem(dist,INF);
	dist[0][1]=0;//
	priority_queue<node> heap;
	heap.push({
   0,1,0});
	while(heap.size())
	{
   
	   node tmp = heap.top();
	   heap.pop();
	   int day = tmp.day,p = tmp.p,val= tmp.val;
	   //如果在那天到达过点p，那么就继续下一次循环 
	   if(vis[day][p]) continue;
	   vis[day][p] = 1;
	   for(int i=h[p]; i!=-1; i=ne[i])
	   {
   
	   		if(day+1>k) continue;
	   	 	int j = e[i];//与i相连的点j
	   	 	//如果第day+1天到大点j的总花费大于第day天达到p的再花一天到达j的总花费
			//那么更新dist数组 
			if(dist[day+1][j]>val+a[day+1]+w[i])
			{
   
			    dist[day+1][j] = a[day+1]+val+w[i];
			    heap.push({
   day+1,j,dist[day+1][j]});
			} 
	   }	
	}
}
int main() {
   
	mem(h,-1);
	cin>>n>>m>>k;
	for(int i=0; i<m; i++)
	{
   
    	int x,y,z;
// a =Read();
// b = Read();
// c = Read();
		cin>>x>>y>>z;
		add(x,y,z);
		add(y,x,z);
	}
	for(int i=1; i<=k; i++)
	{
   
		cin>>a[i];
	}
	Dijstra();
	ll ans = INF;
	for(int i=1; i<=k; i++)
	   ans = min(ans,dist[i][n]);
	if(ans==INF) printf("-1");
	else cout<<ans<<endl;
	return 0;
}