是tle还是wa
by Let_Fly @ 2023-08-23 14:26:46
@[Let_Fly](/user/760859) WA
by ForMyDream @ 2023-08-23 14:27:45
@[ForMyDream](/user/502758)
> rt，用双端队列广搜能 AC，用 Dijkstra 就不行，求解答，谢谢。#include<iostream>#include<cstring>#include<queue>#include<dequ……
分层图没搞对吧
by wwwidk1234 @ 2023-08-23 14:29:46
@[ForMyDream](/user/502758)
> rt，用双端队列广搜能 AC，用 Dijkstra 就不行，求解答，谢谢。#include<iostream>#include<cstring>#include<queue>#include<dequ……
```cpp
signed main()
{
n=read();
m=read();
k=read();
int s=1,t=n;
for(int i=0;i<m;i++)
{
int u=read(),v=read(),w=read();
addEdge(u,v,w);
addEdge(v,u,w);
//写分层图
for(int j=1;j<=k;j++)
{
//其余k层同层连边
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);
}
}
//连层与层的终点
for(int i=1;i<=k;i++) addEdge(t+(i-1)*n,t+i*n,0);
memset(distanc,0x3f,sizeof distanc);
dijkstra(s);
// for(int i=1;i<=t+k*n;i++) cout<<i<<':'<<distanc[i]<<",";
if(distanc[t+n*k]==0x3f3f3f3f) cout<<"-1";
else cout<<distanc[t+n*k];
// cout<<(distanc[t+n*k]==0x3f3f3f3f)?(-1):(distanc[t+n*k]);
return 0;
}
```
by wwwidk1234 @ 2023-08-23 14:30:38
@[wwwidk1234](/user/728483) 用 Dij 一定要用分层图吗，这里我想二分直接替换分层图
by ForMyDream @ 2023-08-23 14:31:05
@[ForMyDream](/user/502758)
> @[wwwidk1234](/user/728483) 用 Dij 一定要用分层图吗，这里我想二分直接替换分层图
我建议是写分层图，这样子就可以直接套模板了，毕竟多连几条边也不是什么难得问题，考虑一下这个：
- 先连普通边
- 其余 $k$ 层同层连边
- 相邻两层连边
具体可以参考我的代码
by wwwidk1234 @ 2023-08-23 14:33:05
你优先队列排序如果用pair要传负数
by Let_Fly @ 2023-08-23 14:33:43
@[Let_Fly](/user/760859) 他已经用 greater 了
by Argvchs @ 2023-08-23 14:36:29
@[Argvchs](/user/533270) 不是注释掉了吗
by Let_Fly @ 2023-08-23 14:40:39
@[Let_Fly](/user/760859) 啊看错了
by Argvchs @ 2023-08-23 14:41:18