1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
| #include<iostream>
#include<cstdio>
#include<queue>
#define ll long long
using namespace std;
namespace Ehnaev{
inline ll read() {
ll ret=0,f=1;char ch=getchar();
while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
return ret*f;
}
inline void write(ll x) {
static char buf[22];static ll len=-1;
if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
while(len>=0) putchar(buf[len--]);
}
}using Ehnaev::read;using Ehnaev::write;
inline void writes(ll x) {write(x);putchar(32);}
const ll N=2e6,inf=1e15;
ll n,m,s,cnt,tot,rt1,rt2;
ll ver[N*2+5],nxt[N*2+5],wt[N*2+5],head[N+5];
bool vis[N+5];
struct node{
ll d,v;
inline bool operator>(const node& rhs) const{return v>rhs.v;}
}t;
struct Sgt{
ll ls,rs,dat;
#define ls(x) tree[x].ls
#define rs(x) tree[x].rs
#define dat(x) tree[x].dat
}tree[N+5];
inline void Dij(ll x) {
priority_queue<node,vector<node>,greater<node> > q;
dat(x)=0;t.v=dat(x);t.d=x;q.push(t);
while(!q.empty()) {
ll h=q.top().d;q.pop();
if(vis[h]) continue;vis[h]=1;
for(ll i=head[h];i;i=nxt[i]) {
if(dat(h)+wt[i]<dat(ver[i])) {
dat(ver[i])=dat(h)+wt[i];
t.d=ver[i];t.v=dat(ver[i]);q.push(t);
}
}
}
}
inline void Addedge(ll u,ll v,ll w) {
ver[++tot]=v;wt[tot]=w;nxt[tot]=head[u];head[u]=tot;
}
inline void Build(ll p,ll l,ll r,ll op) {
dat(p)=inf;
if(l==r) return;ll mid=(l+r)>>1;
cnt++;ls(p)=cnt;Build(ls(p),l,mid,op);
cnt++;rs(p)=cnt;Build(rs(p),mid+1,r,op);
if(op==1) {Addedge(p,ls(p),0);Addedge(p,rs(p),0);}
if(op==2) {Addedge(ls(p),p,0);Addedge(rs(p),p,0);}
}
inline ll Find(ll p,ll lp,ll rp,ll x) {
if(lp==rp) return p;ll mid=(lp+rp)>>1;
if(x<=mid) return Find(ls(p),lp,mid,x);
return Find(rs(p),mid+1,rp,x);
}
inline void Add(ll p,ll lp,ll rp,ll l,ll r,ll u,ll w,ll op) {
if(lp>=l&&rp<=r) {if(op==2) Addedge(u,p,w);else Addedge(p,u,w);return;}
ll mid=(lp+rp)>>1;
if(l<=mid) Add(ls(p),lp,mid,l,r,u,w,op);
if(r>mid) Add(rs(p),mid+1,rp,l,r,u,w,op);
}
inline ll Ask(ll p,ll lp,ll rp,ll x) {
if(lp==rp) {if(dat(p)==inf) return -1;return dat(p);}
ll mid=(lp+rp)>>1;
if(x<=mid) return Ask(ls(p),lp,mid,x);
return Ask(rs(p),mid+1,rp,x);
}
int main() {
n=read();m=read();s=read();
cnt++;rt1=cnt;cnt++;rt2=cnt;
Build(rt1,1,n,1);Build(rt2,1,n,2);
for(ll i=1;i<=m;i++) {
ll op;op=read();
if(op==1) {
ll u,v,w;u=read();v=read();w=read();
u=Find(rt2,1,n,u);Add(rt1,1,n,v,v,u,w,2);
}
if(op==2) {
ll v,l,r,w;v=read();l=read();r=read();w=read();
v=Find(rt2,1,n,v);Add(rt1,1,n,l,r,v,w,2);
}
if(op==3) {
ll v,l,r,w;v=read();l=read();r=read();w=read();
v=Find(rt1,1,n,v);Add(rt2,1,n,l,r,v,w,3);
}
}
for(ll i=1;i<=n;i++) {
ll x,y;x=Find(rt1,1,n,i);y=Find(rt2,1,n,i);
Addedge(x,y,0);Addedge(y,x,0);
}
s=Find(rt2,1,n,s);Dij(s);
for(ll i=1;i<=n;i++) {writes(Ask(rt1,1,n,i));}
return 0;
}
|
