@[Ning24](/user/1137805) 你确定这是 `dijkstra`
```
#include <bits/stdc++.h>
using namespace std;
#define hh printf("\n")
#define kg printf(" ")
//#define int long long
//#define int __int128
namespace quickread{
inline int read(){
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline void write(int x){
if(x<0){putchar('-');x=-x;}
if(x>9)write(x/10);
putchar(x%10+'0');
}
inline string readstr(){
char ch=getchar();string str="";
while(!(ch>='0'&&ch<='9')&&!(ch>='a'&&ch<='z')&&!(ch>='A'&&ch<='Z')) ch=getchar();
while((ch>='0'&&ch<='9')||(ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')){str+=ch;ch=getchar();}
return str;
}
inline char readchar(){
char ch=getchar();
while(!(ch>='0'&&ch<='9')&&!(ch>='a'&&ch<='z')&&!(ch>='A'&&ch<='Z')) ch=getchar();
return ch;
}
}
using namespace quickread;
const int N=1e4+10;
int n,m,s,dis[N];
struct csp{
int x,s;
};
bool operator > (const csp& a,const csp& b){
return a.s>b.s;
}
struct edge{
int v,w;
};
vector<edge>pic[N];
void dijkstra(int u,int s){
for(int i=1;i<=n;i++) dis[i]=2147483647;
priority_queue<csp ,vector<csp> ,greater<csp> >q;
q.push(csp{u,s});
dis[u]=s;
while(!q.empty()){
u=q.top().x,s=q.top().s;q.pop();
for(edge tx:pic[u]){
int v=tx.v,w=tx.w;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
q.push(csp{v,dis[v]});
}
}
}
for(int i=1;i<=n;i++) write(dis[i]),kg;
}
signed main(){
// ios::sync_with_stdio(0);
// cin.tie();cout.tie();
n=read(),m=read(),s=read();
for(int i=1;i<=m;i++){
int u=read(),v=read(),w=read();
pic[u].push_back(edge{v,w});
}
dijkstra(s,0);
return 0;
}
```
by danlao @ 2024-04-04 17:45:43
@[yaodiguoan](/user/1023793) 是没有经过堆优化的dijkstra，时间复杂度是O（n^2），这题的数据范围不会超时，但是WA了
by Ning24 @ 2024-04-04 19:32:42
@[Ning24](/user/1137805) 那你看眼题解
by danlao @ 2024-04-04 19:37:07