wa #4
by 为依相逢 @ 2019-06-11 15:33:19
@[zlym](/space/show?uid=49453) .......
by h_s_c @ 2019-06-11 15:49:06
@[zlym](/space/show?uid=49453) 不会
by h_s_c @ 2019-06-11 15:49:20
@[zlym](/space/show?uid=49453) 代码风格好奇怪。是dijstra吗？为什么不用STL的priority_queue？优先队列，可实现大根堆，小根堆，不用手写堆了。（建议学一下，很好用的）
by 传奇英雄 @ 2019-06-11 15:53:26
@[zlym](/space/show?uid=49453) 这不dijkstra +堆优化吗？
by Strong_Jelly @ 2019-06-11 15:53:27
@[zlym](/space/show?uid=49453) orz 神仙手写堆
by NaCly_Fish @ 2019-06-11 15:53:57
@[NaCly_Fish](/space/show?uid=115864) zlym是我们机房第一大佬
by h_s_c @ 2019-06-11 15:54:47
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<utility>
using namespace std;
const int g=100005,h=400005;
int n,m,t,x[h],y[h],z[g],w[h],s=0;
int xx,yy,zz,d[g],m1,m2,m3;
priority_queue< pair<long long,int> > q;
void f(int xx,int yy)
{
x[++s]=z[xx];
y[s]=yy;
z[xx]=s;
w[s]=zz;
}
int main()
{
//freopen("in","r",stdin);
scanf("%d%d%d",&n,&m,&t);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&xx,&yy,&zz);
f(xx,yy);
}
for(int i=1;i<=n;i++)
d[i]=2000000005;
d[t]=0;
q.push(make_pair(0,t));
while(q.size())
{
m1=-q.top().first;
m2=q.top().second;
q.pop();
if(m1==d[m2])
for(int i=z[m2];i;i=x[i])
{
m3=m1+w[i];
if(m3<d[y[i]])
{
d[y[i]]=m3;
q.push(make_pair(-m3,y[i]));
}
}
}
for(int i=1;i<=n;i++)
printf("%d ",d[i]);
return 0;
}
```
by 传奇英雄 @ 2019-06-11 15:54:52
@[传奇英雄](/space/show?uid=61602) 666
by h_s_c @ 2019-06-11 15:55:27
@[h_s_c](/space/show?uid=164333) orz
by NaCly_Fish @ 2019-06-11 15:56:10