如果数据无法下载怎么办？
by 爱喝敌敌畏 @ 2019-06-05 14:03:07
```cpp
#include<iostream>
#include<cstring>
#include<algorithm>
#include<stdio.h>
#include<queue>
#define MAXN 500088
#define INF 0x3f3f3f3f
using namespace std;
struct edge{
int u,dis,v;
}e[MAXN];
int dis[MAXN],h[MAXN],vis[MAXN],cnt,n,m,s;
inline void add_edge(int u,int v,int d)
{
cnt++;
e[cnt].dis=d;e[cnt].u=v;e[cnt].v=h[u];h[u] = cnt;
}
struct node{
int dis,pos;
bool operator < (const node x) const{
return x.dis<dis;
}
};
priority_queue<node> q;
void dijkstra()
{
memset(dis,INF,sizeof(dis));
dis[s]=0;
q.push((node){0,s});
while(!q.empty()){
node tmp=q.top();
q.pop();
int x=tmp.pos,d=tmp.dis;
if(vis[x])
continue;
vis[x]=1;
for(int i=h[x];i;i=e[i].v){
int y=e[i].u;
if(dis[y]>dis[x]+e[i].dis){
dis[y]=dis[x]+e[i].dis;
if(!vis[y]){
q.push((node){dis[y],y});
}
}
}
}
}
int main()
{
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=m;i++){
int u,v,d;
scanf("%d%d%d",&u,&v,&d);
add_edge(u,v,d);
}
dijkstra();
for(int i=1;i<=n;i++)
printf("%d ",dis[i]);
return 0;
}
by charliegong @ 2019-06-05 14:03:25
@[敌敌畏](/space/show?uid=65602)
```cpp
// luogu-judger-enable-o2
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int n, m, s, x, y, z, num, head[1000001], dis[1000001];
bool vis[1000001];
priority_queue < pair < int, int >, vector < pair < int, int > >, greater < pair < int, int > > > pru;
struct node
{
int next, to, val;
}stu[1000001];
inline void adl(int x, int y, int z)
{
++num;
stu[num].to = y;
stu[num].val = z;
stu[num].next = head[x];
head[x] = num;
}
inline void dijkstra(int s)
{
memset(vis, false, sizeof(vis));
memset(dis, INF, sizeof(dis));
dis[s] = 0;
pru.push(make_pair(0, s));
while(!pru.empty())
{
int u = pru.top().second;
pru.pop();
if(!vis[u])
{
vis[u] = true;
for(register int i = head[u]; i; i = stu[i].next)
{
if(dis[stu[i].to] > dis[u] + stu[i].val)
{
dis[stu[i].to] = dis[u] + stu[i].val;
pru.push(make_pair(dis[stu[i].to], stu[i].to));
}
}
}
}
return;
}
int main()
{
scanf("%d %d %d", &n, &m, &s);
for(register int i = 1; i <= m; ++i)
{
scanf("%d %d %d", &x, &y, &z);
adl(x, y, z);
}
dijkstra(s);
for(register int i = 1; i <= n; ++i)
{
printf("%d ", dis[i]);
}
return 0;
}
```
by Strong_Jelly @ 2019-06-05 14:06:53
堆优化的话，为什么不考虑一下下优先队列呢，QWQ
by 忘尘漪 @ 2019-06-05 15:46:19
@[忘尘漪](/space/show?uid=12346) 堆优化的话时间复杂度是$O(n+mlogn)$
但是配对堆的话是$O(nlogn+m)$
by 爱喝敌敌畏 @ 2019-06-05 21:40:31
@[敌敌畏](/space/show?uid=65602) 打扰了，是我无知了，QAQ
by 忘尘漪 @ 2019-06-05 21:55:04
@[忘尘漪](/space/show?uid=12346) 其实我也很菜QAQ
by 爱喝敌敌畏 @ 2019-06-06 19:08:25
@[敌敌畏](/space/show?uid=65602) 您说笑了QAQ，我都不知道配对堆
by 忘尘漪 @ 2019-06-07 15:32:56
@[忘尘漪](/space/show?uid=12346) 我终于知道哪里错了！！！
by 爱喝敌敌畏 @ 2019-06-10 13:38:03
@[爱喝敌敌畏](/space/show?uid=65602) 恭喜大佬，蒟蒻再次%%%
by 忘尘漪 @ 2019-06-10 14:56:08