大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最少要流的血量。
【说明】
对于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.
题解：
30分做法：
留意到有30%的数据k=0，所以直接SPFA
50分做法：
对于k=1的数据，起点跑一次SPFA，终点跑一次SPFA，然后枚举每条边a->b，用起点到a的最短路+终点到b的最短路更新ans即可。
100分做法：
把SPFA的距离数组改成2维的，令d[i][j]代表起点到点i用了j个急救包后的最短路。
然后SPFA的松弛改成两种情况：用急救包和不用。
最后的答案就是min{d[t][i]}(0<=i<=k)
这样就成功解决了本题。
代码：
#include <iostream> #include <vector> #include <cstdio> #include <algorithm> #include <queue> #include <cstring> using namespace std; #define MAXN 10001 #define MAXK 11 vector<int> edge[MAXN],we[MAXN]; int d[MAXN][MAXK],n,m,k; struct node{ int city,used; node():city(0),used(0){} node(int a,int b):city(a),used(b){} }; void spfa(int x) { queue<node> q; q.push(node(x,0)); for(int i=1;i<=n;++i) { for(int j=0;j<=k;++j) d[i][j]=1000000000; } for(int i=0;i<=k;++i) d[x][i]=0; do { node u=q.front(); q.pop(); for(unsigned i=0;i<edge[u.city].size();++i) { int v=edge[u.city][i],w=we[u.city][i]; if(d[v][u.used]>d[u.city][u.used]+w) { d[v][u.used]=d[u.city][u.used]+w; q.push(node(v,u.used)); } if(u.used<k && d[v][u.used+1]>d[u.city][u.used]) { d[v][u.used+1]=d[u.city][u.used]; q.push(node(v,u.used+1)); } } } while(!q.empty()); } int main() { int u,v,w,s,t; scanf("%d%d%d%d%d",&n,&m,&k,&s,&t); ++s; ++t; for(int i=1;i<=m;++i) { scanf("%d%d%d",&u,&v,&w); ++u; ++v; edge[u].push_back(v); we[u].push_back(w); edge[v].push_back(u); we[v].push_back(w); } spfa(s); int ans=2147483647; for(int i=0;i<=k;++i) { ans=min(ans,d[t][i]); } printf("%d\n",ans); }