@[osmanlin](/user/668649) dij 内 d 数组初始化错了,范围应该是 $[0,t+k\times n]$
by Nt_Tsumiki @ 2023-08-14 17:09:51
```cpp
#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
const int N=5e6+10;
const int INF=0x3f3f3f3f;
using namespace std;
int n,m,k,s,t,tot,to[N],head[N],edge[N],ne[N],d[N],v[N],ans=INF;
priority_queue<pair<int , int > >q;
void add(int x,int y,int z)
{
to[++tot]=y;
edge[tot]=z;
ne[tot]=head[x];
head[x]=tot;
}
void dij()
{
for(int i=0;i<=t+k*n;i++)
{
d[i]=INF;
}
d[s]=0;
q.push(make_pair(0,s));
while(q.size())
{
int x=q.top().second;
q.pop();
if(v[x])
{
continue;
}
v[x]=1;
for(int i=head[x];i;i=ne[i])
{
int y=to[i],z=edge[i];
if(d[y]>d[x]+z)
{
d[y]=d[x]+z;
if(!v[y])q.push(make_pair(-d[y],y));
}
}
}
}
int main()
{
cin>>n>>m>>k>>s>>t;
s++,t++;
for(int i=1;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
++x, ++y;
add(x,y,z);
add(y,x,z);
for (int j = 1; j <= k;j++)
{
add(x+ (j - 1) * n,y+ j * n, 0);
add(y+ (j - 1) * n,x+ j * n, 0);
add(x+ j * n,y+ j * n,z);
add(y+ j * n,x+ j * n,z);
}
}
dij();
for (int i = 0; i <= k; i++) ans = min(ans, d[t+ i * n]);
cout<<ans<<endl;
return 0;
}
```
by Nt_Tsumiki @ 2023-08-14 17:10:35
@[Nt_Tsumiki](/user/420129) 谢谢大佬,问题已解决
by osmanlin @ 2023-08-14 17:24:46
@[Nt_Tsumiki](/user/420129) 然而实际上应该是$[0,n+k\times n]$
by h_rains @ 2023-09-13 11:44:41