Island 发生了一场暴乱！现在 Rinne 要和 Setsuna 立马到地上世界去。
众所周知：Island 是有一些奇怪的城镇和道路构成的（题目需要，游戏党勿喷），有些城镇之间用双向道路连接起来了，且每条道路有它自己的距离。但是有一些城镇已经被派兵戒严，虽然主角可以逆天改命强闯，但是为了体验该游戏的平衡性，他们只能穿过不超过 K 次被戒严的城镇。
定义“穿过”：从一个戒严的点出发到达任意一个点，都会使得次数加1
现在他们想从 1 号城镇最快的走到 n 号城镇（即出口），现在他们想让你告诉他们最短需要走多少路。

输入描述:
第一行三个整数 n,m,k，分别表示城镇数量，边数量和最多能闯过被戒严的城市的次数。
接下来 n 行，每行一个整数 1 或 0，如果为 1 则表示该城市已被戒严，0 则表示相反。
接下来 m 行，每行三个数 u,v,w，表示在 u 城镇和 v 城镇之间有一条长度为 w 的双向道路。

输出描述:
输出一行一个数字，表示从 1 到 n 的最短路径，如果到达不了的话，请输出 -1。
示例1
输入
4 5 1
1
0
1
0
1 2 10
2 3 10
3 1 15
1 4 60
3 4 30
输出
60

#include<bits/stdc++.h>
using namespace std;
struct edge
{
    int to, next, w;
}e[8100];
struct node
{
    int u, k, d;
    node(){}
    node(int u, int k, int d) : u(u), k(k), d(d){}
    bool operator < (const node &a) const
	{
        return d > a.d;
    }
};
int head[888], num,jy[888],n, m, k, d[888];
void add(int u, int v, int w)
{
    e[num].to = v;
    e[num].next = head[u];
    e[num].w = w;
    head[u] = num++;
}
void bfs()
{
    memset(d, -1, sizeof d);
    d[1] = 0;
    priority_queue<node> q;
    q.push(node(1, 0, 0));
    while(!q.empty())
	{
        node cur = q.top();
        q.pop();
        if(cur.u == n)
		{
            printf("%d\n", d[n]);
            return;
        }
        for(int i=head[cur.u];i!=-1;i=e[i].next)
		{
            int v = e[i].to;
            if(jy[cur.u] && cur.k == k) continue;
            if(d[v]==-1|| d[v] > cur.d+e[i].w)
			{
                d[v] = cur.d+e[i].w;
                q.push(node(v,cur.k+jy[cur.u],d[v]));
            }
        }
    }
    puts("-1");
    return;
}
int main()
{
    memset(head, -1, sizeof head);
    num = 0;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++) scanf("%d", &jy[i]);
    for(int i=0;i<m;i++)
	{
        int u, v, w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w), add(v,u,w);
    }
    bfs();
    return 0;
}