```cpp
// luogu-judger-enable-o2
#include<iostream>
#include<fstream>
#include<queue>
#include<cstring>
#include<stdio.h>
using namespace std;
struct Edge{
int dis,to,next;
}edge[100010];
int hd[10010],jsq,s,n,m,k,t,a,b,c;
void add(int u,int v,int dis)
{
jsq++;
edge[jsq].to=v;
edge[jsq].dis=dis;
edge[jsq].next=hd[u];
hd[u]=jsq;
}
struct st{
int now,use;
}w,now;
queue<st> q;
int f[10010][15];
bool vis[10010][15];
void SPFA()
{
memset(f,10,sizeof(f));
now.now=s;
now.use=0;
f[s][0]=0;
q.push(now);
vis[s][0]=true;
while (!q.empty())
{
now=q.front();
q.pop();
vis[now.now][now.use]=false;
for (int i=hd[now.now];i;i=edge[i].next)
{
if (f[edge[i].to][now.use]>f[now.now][now.use]+edge[i].dis)
{
f[edge[i].to][now.use]=f[now.now][now.use]+edge[i].dis;
if (!vis[edge[i].to][now.use])
{
w.now=edge[i].to;
w.use=now.use;
q.push(w);
vis[edge[i].to][now.use]=true;
}
}
if (now.use<k&&f[edge[i].to][now.use+1]>f[now.now][now.use])
{
f[edge[i].to][now.use+1]=f[now.now][now.use];
if (!vis[edge[i].to][now.use+1])
{
w.now=edge[i].to;
w.use=now.use+1;
q.push(w);
vis[edge[i].to][now.use+1]=true;
}
}
}
}
}
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
int main()
{
n=read(); m=read(); k=read(); //scanf("%d %d %d",&n,&m,&k);//cin>>n>>m>>k;
s=read(); t=read();//scanf("%d %d",&s,&t);//cin>>s>>t;
for (int i=1;i<=m;i++)
{
a=read(); b=read(); c=read();//scanf("%d %d %d",&a,&b,&c);//cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
}
SPFA();
int ans=999999999;
for (int i=0;i<=k;i++)ans=min(ans,f[t][i]);
printf("%d",ans);//cout<<ans<<endl;
return 0;
}
```
by Smile_Cindy @ 2019-06-01 21:32:28
没发现有什么改动啊。
by 人生如此 @ 2019-08-17 08:50:05