下面是你的代码
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=5000;
int g[N][N],d[9000];
bool st[N];
int n,m,s;
void dijkstra(int s){
memset(d,0x3f,sizeof(d));
d[s]=0;
for(int i=1;i<=n;i++){
int t=-1;
for(int j=s;j<=n;j++){
if(!st[j]&&(t==-1||d[t]>d[j])){
t=j;
}
}
for(int j=1;j<=s;j++){
if(!st[j]&&(t==-1||d[t]>d[j])){
t=j;
}
}
st[t]=1;
for(int j=1;j<=n;j++){
d[j]=min(d[j],d[t]+g[t][j]);
}
}
}
int main(){
cin>>n>>m>>s;
memset(g,0x3f,sizeof(g));
while(m--){
int u,v,w;
cin>>u>>v>>w;
g[u][v]=min(g[u][v],w);
}
dijkstra(s);
for(int i=1;i<=n;i++){
cout<<d[i]<<" ";
}
}
```
第一个问题:$\LARGE\text\color{purple}{RE}$
题目说了,$n \le 10^4$,而你的$N$只开到了$5000$,数组越界了
第二个问题:取最小值
其实你那样写也可以,不过完全可以写成$i = 1,i \le n$,而不用从起点分成$2$段
至于$\LARGE\text\color{red}{WA}$...十有八九因为数组越界了一点点导致的
还有,你说啥邻接表用结构体存,没见着代码啊
@[DicaprioD](/user/946114)
by QWQ_HY_DFX @ 2024-02-21 09:31:49
哦...等等,你$d$和$st$数组也开小了...至少开到$10^4$
by QWQ_HY_DFX @ 2024-02-21 09:37:32
@[DicaprioD](/user/946114) 请仔细看数据范围。题目给定的 $n \leq 10^4$ ,所以邻接矩阵存不下,请使用邻接表存边。
by xixisuper @ 2024-02-21 09:43:53
邻接矩阵容易$\LARGE\text\color{black}{MLE}$,这边建议$vector$邻接表
还有,要防止$\LARGE\text\color{black}{TLE}$,建议写堆优化
@[DicaprioD](/user/946114)
by QWQ_HY_DFX @ 2024-02-21 09:47:41
@[QWQ_HY_DFX](/user/750772)
感谢大佬,我还是回去好好学学优先队列吧
orz orz
邻接表存储看着怪麻烦的,所以我学的跟勾石一样,不想用也不会用(尤其不知道Dijkstra部分该咋写),所以想求一份板子去背hh
by DicaprioD @ 2024-02-21 10:06:26
@[xixisuper](/user/580107)
本蒟蒻不太会邻接表,故发此贴球一份板子,想背hh
感谢大佬hh
by DicaprioD @ 2024-02-21 10:09:32
@[QWQ_HY_DFX](/user/750772)
邻接表不会用,没有写代码~
我看题解的邻接表都是struct的,看着就不想写
所以很想要一份数组版的邻接表学习一下
故发此贴
orz orz
by DicaprioD @ 2024-02-21 10:13:58
因为邻接表要存点和边权,所以用$struct$
当然也可以用$pair$,不过据说$pair$比较慢...但$pair$也有它的好处,就是不用重载运算符
反正我自己是用结构体+重载运算符,不过我的同学好像大部分都用$pair$...
@[DicaprioD](/user/946114)
by QWQ_HY_DFX @ 2024-02-21 10:24:41
$vector$邻接表用习惯之后就知道有多好用了,而且写法简单
by QWQ_HY_DFX @ 2024-02-21 10:25:53
@[QWQ_HY_DFX](/user/750772)
在学pair了~~
by DicaprioD @ 2024-02-21 10:42:38