@[Rebirth_Yun](/user/905233) 要在每一层图中找最小，最后一层不一定是最小的
by YeHaiFengYC2204 @ 2023-08-10 10:01:24
最后面的for循环是没用的，删掉
by YeHaiFengYC2204 @ 2023-08-10 10:02:31
@[YeHaiFengYC2204](/user/561482)
我把最后改成了
```cpp
Dijkstra();
long long ans=inf;
for(int j=0;j<=k;j++)
if(dis[t+j*n]<ans)
ans = dis[t+j*n];
cout << ans;
```
但好像还是WA了 我感觉这么写没毛病哇
by Rebirth_Yun @ 2023-08-10 10:09:08
先说一些小问题：1,dijkstra开头初始化了dis两遍。2,默认情况下，优先队列从大到小，你要手动换成greater
by YeHaiFengYC2204 @ 2023-08-10 10:15:27
@[Rebirth_Yun](/user/905233)
by YeHaiFengYC2204 @ 2023-08-10 10:15:37
其他就没有问题了
by YeHaiFengYC2204 @ 2023-08-10 10:16:32
@[YeHaiFengYC2204](/user/561482)
emmm
```cpp
#include<bits/stdc++.h>
using namespace std;
const long long maxn = 2500001;
const long long inf = 0x3f3f3f3f;
long long n,m,s,cnt;
long long k,t;
long long dis[maxn],h[maxn],nxt[maxn],to[maxn],val[maxn];
bool vis[maxn];
void add(long long a,long long b,long long c=0)
{
to[++cnt] = b;
val[cnt] = c;
nxt[cnt] = h[a];
h[a] = cnt;
}
struct node
{
long long v,w;
friend bool operator> (node a,node b)
{
return a.w>b.w;
}
}tmp;
priority_queue <node,vector<node>,greater<node> >q;
void Dijkstra()
{
memset(vis,0,sizeof(vis));
memset(dis,inf,sizeof(dis));
dis[s]=0;
tmp.v = s,tmp.w=0;
q.push(tmp);
while (!q.empty())
{
long long u = q.top().v;
q.pop();
if(vis[u])
continue;
vis[u]=1;
for(long long i=h[u];i;i=nxt[i])
{
if(dis[to[i]]>(long long)dis[u]+val[i])
{
dis[to[i]]=dis[u]+val[i];
tmp.w = dis[to[i]],tmp.v=to[i];
q.push(tmp);
}
}
}
return;
}
int main()
{
::ios_base::sync_with_stdio(false);
memset(h,-1,sizeof(h));
cin >>n>>m>>k>>s>>t;
for(long long i=0,u,v,w;i<m;i++)
{
cin >> u >> v >> w;
add(u,v,w);
add(v,u,w);
for(long long j=1; j<=k; j++)
{
add(u+(j*n),v+(j*n),w);
add(v+(j*n),u+(j*n),w);
add(u+(j-1)*n,v+(j*n));
add(v+(j-1)*n,u+(j*n));
}
}
Dijkstra();
long long ans=inf;
for(int j=0;j<=k;j++)
if(dis[t+j*n]<ans)
ans = dis[t+j*n];
cout << ans;
return 0;
}
```
奇怪就奇怪在还在不太知道咋错了T T
by Rebirth_Yun @ 2023-08-10 10:37:55
@[Rebirth_Yun](/user/905233) 找了好久，又发现了一个问题：vis[s]你没有设为1。然而我试过了，样例都过不了，输出一个很大的数
by YeHaiFengYC2204 @ 2023-08-10 10:52:46
@[YeHaiFengYC2204](/user/561482)
谢谢大佬 辛苦了
```cpp
dis[s]=0;
tmp.v = s,tmp.w=0;
q.push(tmp);
while (!q.empty())
{
long long u = q.top().v;
q.pop();
if(vis[u])
continue;
vis[u]=1;
for(long long i=h[u];i;i=nxt[i])
{
if(dis[to[i]]>(long long)dis[u]+val[i])
{
dis[to[i]]=dis[u]+val[i];
tmp.w = dis[to[i]],tmp.v=to[i];
q.push(tmp);
}
}
}
```
我的vis[s]会以第一个元素进入 所以这个应该没关系吧
我下午接着找找错555
by Rebirth_Yun @ 2023-08-10 11:02:39
@[Rebirth_Yun](/user/905233) 帮你盖好了,[这里](https://www.luogu.com.cn/record/120023017)
by YeHaiFengYC2204 @ 2023-08-10 11:22:14