2 、 行动 ！行动 ！(move) 

题目描述：

大 CX 国的大兵 Jack 接到一项任务：敌方占领了 n 座城市（编号 0~n-1），
有些城市之间有双向道路相连。Jack 需要空降在一个城市 S，并徒步沿那些道路
移动到 T 城市。虽然 Jack 每从一个城市到另一个城市都会受伤流血，但大 CX
国毕竟有着“过硬”的军事实力，它不仅已经算出 Jack 在每条道路上会损失的
血量，还给 Jack 提供了 k 个“简易急救包”，一个包可以让 Jack 在一条路上的
流血量为 0。Jack 想知道自己最少会流多少血，不过他毕竟是无脑的大兵，需要
你的帮助。

输入描述：

第一行有三个整数 n,m,k，分别表示城市数，道路数和急救包个数。
第二行有两个整数，S,T。分别表示 Jack 空降到的城市编号和最终要到的城
市。
接下来有 m 行，每行三个整数 a,b,c，表示城市 a 与城市 b 之间有一条 双向
道路。

输出描述：

Jack 最少要流的血量。

样例输入：

5 6 1
0 3
3 4 5
0 1 5
0 2 100
1 2 5
2 4 5
2 4 3

样例输出：

8

数据范围：

对于 30%的数据,2<=n<=50,1<=m<=300,k=0；
对于 50%的数据,2<=n<=600,1<=m<=6000,0<=k<=1；
对于 100%的数据,2<=n<=10000,1<=m<=50000,0<=k<=10。

思路：

暴力出奇迹
直接BFS（加优先队列优化和最优解优化）

代码 

#include<bits/stdc++.h>
using namespace std;
int n,m,k,s,t;
struct oppo{
	int to,s,next;
}rood[100005];
int head[10005],tot;
void add(int from,int to,int s)
{
	rood[++tot].to=to;
	rood[tot].s=s;
	rood[tot].next=head[from];
	head[from]=tot;
}
struct vivo{
	int x,s,k;
	bool operator<(const vivo x)const{return s>x.s;}
}st;
priority_queue< vivo > v;
int book[10005][20];
int main()
{
	memset(book,127,sizeof(book));
	cin>>n>>m>>k;
	cin>>s>>t;
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
		add(y,x,z);
	}
	st.x=s;
	st.k=k;
	st.s=0;
	v.push(st);
	while(v.size())
	{
		vivo lxl=v.top();
		v.pop();
		if(lxl.x==t)
		{
			cout<<lxl.s<<endl;
			return 0;
		}
		for(int i=head[lxl.x];i;i=rood[i].next)
		{
			if(lxl.k>0)
			{
				st.k=lxl.k-1;
				st.x=rood[i].to;
				st.s=lxl.s;
				if(book[st.x][st.k]>st.s)
				{
					book[st.x][st.k]=st.s;
					v.push(st);
				}
			}
			st.k=lxl.k;
			st.x=rood[i].to;
			st.s=lxl.s+rood[i].s;
			if(book[st.x][st.k]>st.s)
			{
				book[st.x][st.k]=st.s;
				v.push(st);
			}
		}
	}
	return 0;
}