代码见下,求大佬帮忙解决下,谢谢!
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x7f7f7f7f
int n,m,k,s,t;
struct node
{
int id;
int dis;
bool operator< (const node& x) const {
return x.dis < dis;
}
};
struct Edge{
int from, to, weight, next;
}edge[1000010];
int head[1000010], cnt=0;
void addEdge(int u,int v,long long w)
{
edge[cnt].from=u;
edge[cnt].to=v;
edge[cnt].weight=w;
edge[cnt].next=head[u];
head[u]=cnt++;
}
int dis[1000010];
bool vis[1000010];
priority_queue<node>qp;
void dijkstra(int s){
for(int i=1;i<=n;i++) dis[i]=INF;
dis[s]=0; vis[s]=true;
qp.push((node){s,0});
while(!qp.empty())
{
int cntnode=qp.top().id;
qp.pop(); vis[cntnode]=false;
for(int i=head[cntnode]; i!=-1; i=edge[i].next)
{
if(dis[edge[i].to]>dis[cntnode]+edge[i].weight)
{
dis[edge[i].to]=dis[cntnode]+edge[i].weight;
if(!vis[edge[i].to])
{
vis[edge[i].to]=true;
qp.push((node){edge[i].to, dis[edge[i].to]});
}
}
}
}
}
signed main()
{
memset(head, -1, sizeof(head));
memset(dis, 0x7f7f7f7f, sizeof(dis));
cin>>n>>m>>k>>s>>t;
for(int i=1,u,v;i<=m;i++)
{
long long w;
cin>>u>>v>>w;
addEdge(u,v,w);
addEdge(v,u,w);
for(int j=1;j<=k;j++)
{
addEdge(u+j*n,v+j*n,w);
addEdge(v+j*n,u+j*n,w);
addEdge(u+(j-1)*n,v+j*n,0);
addEdge(v+(j-1)*n,u+j*n,0);
}
}
dijkstra(s);
int ans=0x7f7f7f7f;
for(int i=0;i<=k;i++)
{
ans=min(ans, dis[i*n+t]);
}
cout<<ans;
return 0;
}