<题目链接>
题目大意：
Island 是有一些奇怪的城镇和道路构成的（题目需要，游戏党勿喷），有些城镇之间用双向道路连接起来了，且每条道路有它自己的距离。但是有一些城镇已经被派兵戒严，虽然主角可以逆天改命强闯，但是为了体验该游戏的平衡性，他们只能穿过不超过 K 次被戒严的城镇。
定义“穿过”：从一个戒严的点出发到达任意一个点，都会使得次数加1
现在他们想从 1 号城镇最快的走到 n 号城镇（即出口），现在他们想让你告诉他们最短需要走多少路。
2≤n≤800,1≤m≤4000,1≤k≤10,1≤w≤10^6
解题分析：
本题很明显是一道分成图最短路的题。主要的就是怎么处理"穿过"K个点，我是通过在最短路松弛过程中，判断下一个点是否是*点，是的话，就要利用分层图的性质进行松弛。因为题目规定的是穿过k个*点，所以我们需要对起点和终点进行处理。如果起点是*点，那么k--,如果终点是*点k++，因为起点是一定要穿过的，而终点穿不过。
#include <bits/stdc++.h>
using namespace std; #define clr(a,b) memset(a,b,sizeof(a))
#define rep(i,s,t) for(int i=s;i<=t;i++)
typedef long long ll;
const int N = , M = ;
int n,m,k,cnt;
int isgo[N],head[N]; template<typename T>
inline void read(T&x){
x=;int f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar(); }
while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}
x*=f;
}
struct Edge{
int to,nxt;ll w;
}edge[M<<]; struct Node{
int loc,lev;ll dist;
Node(int _loc=,int _lev=,ll _dist=):loc(_loc),lev(_lev),dist(_dist){}
bool operator < (const Node &tmp)const{ return dist>tmp.dist; }
}node[N][];
int vis[N][]; inline void init(){ cnt=;clr(head,-); }
inline void add(int u,int v,ll w){
edge[++cnt].to=v,edge[cnt].nxt=head[u];
edge[cnt].w=w;head[u]=cnt;
}
void Dij(){
rep(i,,n) rep(j,,k){
node[i][j].loc=i,node[i][j].lev=j;
node[i][j].dist=1e18;vis[i][j]=;
}
priority_queue<Node>q;
node[][].dist=;
q.push(node[][]);
while(!q.empty()){
Node now=q.top();q.pop();
int loc=now.loc,lev=now.lev;
if(vis[loc][lev])continue;
vis[loc][lev]=;
for(int i=head[loc];~i;i=edge[i].nxt){
int v=edge[i].to;ll cost=edge[i].w;
if(!isgo[v] && node[v][lev].dist>node[loc][lev].dist+cost){ //进行同层次建进行正常的松弛
node[v][lev].dist=node[loc][lev].dist+cost;
q.push(Node(v,lev,node[v][lev].dist));
}
if(isgo[v] && (lev+)<=k && node[v][lev+].dist>node[loc][lev].dist+cost){ //不是*点的就没有必要利用分层图进行松弛，因为在正常的一层就已经松弛了
node[v][lev+].dist=node[loc][lev].dist+cost;
q.push(Node(v,lev+,node[v][lev].dist));
}
}
}
}
int main(){
init();
read(n);read(m);read(k);
rep(i,,n) read(isgo[i]);
rep(i,,m){
int u,v;ll w;read(u);read(v);read(w);
add(u,v,w);add(v,u,w);
}
if(isgo[])k--;
if(isgo[n])k++;
Dij();
ll ans=1e18;rep(i,,k)ans=min(ans,node[n][i].dist);
printf("%lld\n",ans);
}