Description
每天,农夫John需要经过一些道路去检查牛棚N里面的牛. 农场上有M(1<=M<=50,000)条双向泥土道路,编号为1..M. 道路i连接牛棚P1_i和P2_i (1 <= P1_i <= N; 1 <= P2_i<= N). John需要T_i (1 <= T_i <= 1,000,000)时间单位用道路i从P1_i走到P2_i或者从P2_i 走到P１_i 他想更新一些路经来减少每天花在路上的时间.具体地说,他想更新K (1 <= K <= 20)条路经，将它们所须时间减为0．帮助FJ选择哪些路经需要更新使得从１到N的时间尽量少.
Input
第一行: 三个空格分开的数: N, M, 和 K * 第2..M+1行: 第i+1行有三个空格分开的数：P1_i, P2_i, 和 T_i
Output
第一行: 更新最多Ｋ条路经后的最短路长度．
题目分析
分层图最短路 f[i][j]表示改变j条路径后 从1~i的最短距离
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m,k;
int start,end;
int head[200000];
int next[200000];
int to[200000];
int val[200000];
bool vis[20000][22];
int f[20000][22];
struct your
{
int x,t;
};
int read()
{
int sum=0;
char c;
c=getchar();
while(c==' '||c=='\n')
c=getchar();
while(c<='9'&&c>='0')
sum=(sum<<3)+(sum<<1)+(c-'0'),c=getchar();
return sum;
}
struct cmp
{
bool operator()(const your j,const your k)
{
return f[j.x][j.t]>f[k.x][k.t];
}
};
priority_queue<your,vector<your>,cmp>q;
void spfa()
{
your nmp;
nmp.x=1;
nmp.t=0;
memset(f,0x3f,sizeof f);
f[1][0]=0;
vis[1][0]=1;
q.push(nmp);
while(q.size())
{
nmp=q.top();
q.pop();
vis[nmp.x][nmp.t]=false;
for(int i=head[nmp.x];i;i=next[i])
{
if(f[to[i]][nmp.t]>f[nmp.x][nmp.t]+val[i])
{
f[to[i]][nmp.t]=f[nmp.x][nmp.t]+val[i];
if(!vis[to[i]][nmp.t])
{
your tmp;
tmp.x=to[i];
tmp.t=nmp.t;
vis[to[i]][nmp.t]=true;
q.push(tmp);
}
}
}
if(nmp.t==k) continue;
for(int i=head[nmp.x];i;i=next[i])
{
if(f[to[i]][nmp.t+1]>f[nmp.x][nmp.t])
{
f[to[i]][nmp.t+1]=f[nmp.x][nmp.t];
if(!vis[to[i]][nmp.t+1])
{
your tmp;
tmp.x=to[i];
tmp.t=nmp.t+1;
vis[to[i]][nmp.t+1]=true;
q.push(tmp);
}
}
}
}
}
int tot;
void add(int x,int y,int c)
{
next[++tot]=head[x];
to[tot]=y;
val[tot]=c;
head[x]=tot;
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=m;i++)
{
int x,y,c;
x=read();
y=read();
c=read();
add(x,y,c);
add(y,x,c);
}
spfa();
int ans=0x7f7f7f7f;
for(int i=0;i<=k;i++)
ans=min(ans,f[n][i]);
printf("%d",ans);
return 0;
}
