```cpp
# include <stdio.h> //Dijkstra
# include <string.h>
# include <queue>
# include <iostream>
using namespace std;
int n,m,s,num=0,dis[11451]={0};
int head[11451]={0};
bool vis[11451]={0};
struct Edge{
int from;
int to;
int Next;
int Distance;
}edge[21451];
void AddEdge(int From,int To,int Dis){
edge[++num].Next=head[From];
head[From]=num;
edge[num].from=From;
edge[num].to=To;
edge[num].Distance=Dis;
return;
}
int main(){
scanf("%d%d%d",&n,&m,&s);
for(int i=0;i<m;i++){
int u,v,d;
scanf("%d%d%d",&u,&v,&d);
AddEdge(u,v,d);
}
memset(dis,0x3f,sizeof(dis));
queue<int>qu;
qu.push(1);
dis[1]=0;
vis[1]=1;
while(!qu.empty()){
int Now=qu.front();
qu.pop();vis[Now]=0;
for(int i=head[Now];i;i=edge[i].Next){
if(dis[edge[i].to]>dis[Now]+edge[i].Distance){
dis[edge[i].to]=dis[Now]+edge[i].Distance;
if(!vis[edge[i].to]){
vis[edge[i].to]=1;
qu.push(edge[i].to);
}
}
}
}
for(int i=1;i<=n;i++){
printf("%d ",dis[i]);
}
return 0;
}
```
补一个代码
by 航小怕 @ 2024-01-27 19:55:40
@[航小怕](/user/531454) RE 的原因是数组开小了。
而且你使用的是 SPFA，而这个题是标准版。请使用 dijstra，SPFA 无法通过此题。
by hello_world_djh @ 2024-01-27 19:59:07
@[hello_world_djh](/user/450700) 那为啥我用了Dijkstra也全部RE了
代码：
```cpp
# include <stdio.h> //Dijkstra
# include <string.h>
# include <queue>
# include <iostream>
using namespace std;
int n,m,s,num=0,dis[11451]={0};
int head[11451]={0};
bool vis[11451]={0};
struct Edge{
int from;
int to;
int Next;
int Distance;
}edge[21451];
void AddEdge(int From,int To,int Dis){
edge[++num].Next=head[From];
head[From]=num;
edge[num].from=From;
edge[num].to=To;
edge[num].Distance=Dis;
return;
}
int main(){
scanf("%d%d%d",&n,&m,&s);
for(int i=0;i<m;i++){
int u,v,d;
scanf("%d%d%d",&u,&v,&d);
AddEdge(u,v,d);
}
memset(dis,0x3f,sizeof(dis));
dis[1]=0;
for(int i=0;i<n;i++){
int Minn=0x7fffffff,sd;
for(int j=1;j<=n;j++){
if(dis[j]<Minn&&!vis[j]){
Minn=dis[j];
sd=j;
}
}
vis[sd]=1;
for(int j=head[sd];j;j=edge[j].Next){
if(dis[edge[j].to]>dis[sd]+edge[j].Distance){
dis[edge[j].to]=dis[sd]+edge[j].Distance;
}
}
}
for(int i=1;i<=n;i++){
printf("%d ",dis[i]);
}
return 0;
}
```
by 航小怕 @ 2024-01-27 20:02:47
懂了，数组开大一点了，但是Dijkstra全部TLE（悲，献上代码，大佬求调
```cpp
# include <stdio.h> //Dijkstra
# include <string.h>
# include <queue>
# include <iostream>
using namespace std;
int n,m,s,num=0,dis[114510]={0};
int head[114510]={0};
bool vis[114510]={0};
struct Edge{
int from;
int to;
int Next;
int Distance;
}edge[214510];
void AddEdge(int From,int To,int Dis){
edge[++num].Next=head[From];
head[From]=num;
edge[num].from=From;
edge[num].to=To;
edge[num].Distance=Dis;
return;
}
int main(){
scanf("%d%d%d",&n,&m,&s);
for(int i=0;i<m;i++){
int u,v,d;
scanf("%d%d%d",&u,&v,&d);
AddEdge(u,v,d);
}
memset(dis,0x3f,sizeof(dis));
dis[1]=0;
for(int i=0;i<n;i++){
int Minn=0x7fffffff,sd;
for(int j=1;j<=n;j++){
if(dis[j]<Minn&&!vis[j]){
Minn=dis[j];
sd=j;
}
}
vis[sd]=1;
for(int j=head[sd];j;j=edge[j].Next){
if(dis[edge[j].to]>dis[sd]+edge[j].Distance){
dis[edge[j].to]=dis[sd]+edge[j].Distance;
}
}
}
for(int i=1;i<=n;i++){
printf("%d ",dis[i]);
}
return 0;
}
```
by 航小怕 @ 2024-01-27 20:11:02
@[航小怕](/user/531454) 数组开小了 加个0 Dijskstra需要堆优化
by I_AK_IOI_1114 @ 2024-01-27 20:11:26
楼上正解。
by hello_world_djh @ 2024-01-27 20:12:43
@[I_AK_IOI_1114](/user/772368) 但还是TLE啊
by 航小怕 @ 2024-01-27 20:13:42
@[hello_world_djh](/user/450700) 你写的这个 dijstra 是 $\Theta (n^2)$ 的。堆优化可以做到 $\Theta (n \log n)$。
by hello_world_djh @ 2024-01-27 20:14:01
@[hello_world_djh](/user/450700) 不懂就问，怎么优化
by 航小怕 @ 2024-01-27 20:14:28
@[航小怕](/user/531454) 我讲的不太清楚，你最好百度。
by hello_world_djh @ 2024-01-27 20:15:34