线段树优化dij
哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈
我可能是个智障
// luogu-judger-enable-o2
#pragma GCC diagnostic error "-std=c++11"
#pragma GCC optimize("-fdelete-null-pointer-checks,inline-functions-called-once,-funsafe-loop-optimizations,-fexpensive-optimizations,-foptimize-sibling-calls,-ftree-switch-conversion,-finline-small-functions,inline-small-functions,-frerun-cse-after-loop,-fhoist-adjacent-loads,-findirect-inlining,-freorder-functions,no-stack-protector,-fpartial-inlining,-fsched-interblock,-fcse-follow-jumps,-fcse-skip-blocks,-falign-functions,-fstrict-overflow,-fstrict-aliasing,-fschedule-insns2,-ftree-tail-merge,inline-functions,-fschedule-insns,-freorder-blocks,-fwhole-program,-funroll-loops,-fthread-jumps,-fcrossjumping,-fcaller-saves,-fdevirtualize,-falign-labels,-falign-loops,-falign-jumps,unroll-loops,-fsched-spec,-ffast-math,Ofast,inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2",3)
#pragma GCC target("avx","sse2")
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn =200007;
const int maxm = 500007;
const int INF = 0x7fffffff;
int n,m;
inline int read() {
int x=0;
char c=getchar();
while(c<'0'||c>'9')
c=getchar();
while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
return x;
}
struct node{
int v,next,w;
}edge[maxm];
int num=0,head[maxn];
inline void add_edge(int a,int b,int c) {
edge[++num].v=b;edge[num].w=c;edge[num].next=head[a];head[a]=num;
}
int dis[maxn],ans[maxn],s,t;
int tree[maxn<<2],leaf;
inline int check(int i,int j) {
return dis[i]<dis[j]?i:j;
}
inline void build() {
std::memset(dis,0x3f,sizeof dis);// for(int i=0;i<=n+1;i++) dis[i]=INF;
for(leaf=1;leaf<=n;leaf<<=1);--leaf;
for(int i=1;i<=n;++i)tree[leaf+i]=i;
}
inline void modify(int x,int y) {
dis[x]=y,x+=leaf,x>>=1;
while(x) tree[x]=check(tree[x<<1],tree[x<<1|1]),x=x>>1;
}
void dijkstra(int s) {
build();
dis[s]=0;
int u=s;
for(int i=1;i<=n;++i) {
ans[u]=dis[u];
const int disu=dis[u];
modify(u,INF);
for(int j=head[u];j;j=edge[j].next){
int v=edge[j].v;
if(dis[v]<INF&&dis[v]>disu+edge[j].w)
modify(v,disu+edge[j].w);
}
u=tree[1];
}
}
int main() {
int k;
n=read(),m=read(),k=read();
for(int a,b,c,i=1;i<=m;++i) {
a=read(),b=read(),c=read();
add_edge(a,b,c);
}
dijkstra(k);
for(int i=1;i<=n;++i) {
if(dis[i]==0x3f3f3f3f)ans[i]=INF;
printf("%d ",ans[i]);
}
return 0;
}