# 求大佬帮忙

@zhengjinchen 2020-11-22 11:43 回复

### Dijkstra 我在从 O(n²) 优化到 O(n log n)时候写挂了

//O(n log n)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
inline int getint()
{
char ch=getchar();long long w=0,f=1;
while(ch<'0' || ch>'9'){if(ch=='-')f=-f; ch=getchar();}
while(ch>='0' && ch<='9'){w=(w<<1)+(w<<3)+(ch^48); ch=getchar();}
return w*f;
}

int n,m,tot,start;
const int MAXN=500005;
struct Edge
{
}a[MAXN];
struct Point
{
int dis,number;
bool operator < (const Point &a)const
{
return dis<a.dis;
};
}p[MAXN];
inline bool cmp(Point x,Point y)
{
return x.dis<y.dis;
}
priority_queue<Point> q;

{
tot++;
a[tot].u=y;
a[tot].w=v;
}
inline void Dijkstra(int start)
{
for(register int i=1;i<=n;i++)
{
p[i].number=i;
q.push(p[i]);
}
for(register int i=1;i<=n;i++)
{
Point minn=q.top();q.pop();
int mini=minn.number;
p[a[j].u].dis=min(p[a[j].u].dis,p[mini].dis+a[j].w);
}
p[start].dis=0;
for(int i=1;i<=n;i++)
{
if(p[i].dis!=1000000000) cout<<p[i].dis<<" ";
else cout<<2147483647<<" ";
}
}
int main()
{
for(int i=1;i<MAXN-5;i++) p[i].dis=1000000000;
n=getint();m=getint();start=getint();
for(register int i=1;i<=m;i++)
{
int u,v,w;
u=getint();v=getint();w=getint();
if(u==start) p[v].dis=w;
}
p[start].dis=0;
Dijkstra(start);
return 0;
}
//O(n²)
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
inline int getint()
{
char ch=getchar();long long w=0,f=1;
while(ch<'0' || ch>'9'){if(ch=='-')f=-f; ch=getchar();}
while(ch>='0' && ch<='9'){w=(w<<1)+(w<<3)+(ch^48); ch=getchar();}
return w*f;
}
const int MAXN=500005;
bool vis[MAXN];
{
tot++;
u[tot]=y;
w[tot]=v;
}
int n,m,start;
inline void Dijkstra(int start)
{
for(register int i=1;i<=n;i++)
{
int minn=1e9,mini;
for(register int j=1;j<=n;j++)
{
if(!vis[j] && minn>dis[j])
{
minn=dis[j];
mini=j;
}
}
vis[mini]=true;
dis[u[j]]=min(dis[u[j]],dis[mini]+w[j]);
}
dis[start]=0;
for(int i=1;i<=n;i++)
{
if(dis[i]!=1061109567) cout<<dis[i]<<" ";
else cout<<2147483647<<" ";
}
}
int main()
{
memset(dis,0x3f3f3f,sizeof(dis));
n=getint();m=getint();start=getint();
for(register int i=1;i<=m;i++)
{
int u,v,w;
u=getint();v=getint();w=getint();
}