```cpp
#include<bits/stdc++.h>
using namespace std;
const long long MAXN=100200,INF=1e17+7;
struct segnode
{
long long l,r,id;
};
struct treenode
{
long long id,d;
bool operator > (const treenode &t) const
{
return d>t.d;
}
};
struct edg
{
long long v,d;
};
inline edg eddg(long long v,long long d)
{
edg t;
t.v=v;
t.d=d;
return t;
}
treenode dis[MAXN];
segnode a[MAXN*8];
long long n,q,s,rleaf[MAXN],lleaf[MAXN],vis[MAXN*8];
//vector<edg> edge[MAXN*8];
long long to[MAXN*16],nxt[MAXN*16],hd[MAXN*16],val[MAXN*16],cnt;
void add(long long x,long long y,long long z)
{
to[++cnt]=y;
nxt[cnt]=hd[x];
hd[x]=cnt;
val[cnt]=z;
return;
}
inline void read(long long &x)
{
x=0;
char c=getchar();
while(!(c<='9'&&c>='0'))
{
c=getchar();
}
while(c<='9'&&c>='0')
{
x=(x<<3)+(x<<1)+c-48;
c=getchar();
}
return;
}
inline void pushup(long long x,long long K)
{
if(K==0)
{
// edge[x].push_back(eddg((x<<1),0));
// edge[x].push_back(eddg((x<<1)+1,0));
add(x,x*2,0);
add(x,x*2+1,0);
}
else
{
// edge[(x<<1)+K].push_back(eddg(x+K,0));
// edge[(x<<1)+1+K].push_back(eddg(x+K,0));
add(x*2+K,x+K,0);
add(x*2+1+K,x+K,0);
}
return;
}
void build(long long x,long long l,long long r,long long K)
{
a[x+K].l=l;
a[x+K].r=r;
a[x+K].id=x;
if(l==r)
{
if(K)
{
// edge[x].push_back(eddg(x+K,0));
// edge[x+K].push_back(eddg(x,0));
add(x,x+K,0);
add(x+K,x,0);
rleaf[l]=x+K;
}
else
{
lleaf[l]=x;
}
return;
}
long long mid=(l+r)/2;
build((x<<1),l,mid,K);
build((x<<1)+1,mid+1,r,K);
pushup(x,K);
return;
}
void inc(long long x,long long l,long long r,long long K,long long u,long long val)
{
if(a[x+K].l==l&&a[x+K].r==r)
{
if(K==0)
{
// edge[u].push_back(eddg(x+K,val));
add(u,x,val);
}
else
{
// edge[x+K].push_back(eddg(u,val));
add(x+K,u,val);
}
return;
}
long long mid=(a[x].l+a[x].r)/2;
if(l<=mid)
{
inc((x<<1),l,min(mid,r),K,u,val);
}
if(r>=mid+1)
{
inc((x<<1)+1,max(l,mid+1),r,K,u,val);
}
return;
}
priority_queue<treenode,vector<treenode>,greater<treenode> > lis;
inline void dijkstra()
{
long long i,t,m,k,p;
for(i=1;i<=n*8;i++)
{
dis[i].d=INF;
dis[i].id=i;
dis[i].d=INF;
dis[i].id=i;
}
dis[rleaf[s]].d=0;
lis.push(dis[rleaf[s]]);
while(!lis.empty())
{
t=lis.top().id;
lis.pop();
if(vis[t])
{
continue;
}
vis[t]=1;
// m=edge[t].size()-1;
for(i=hd[t];i>0;i=nxt[i])
{
k=to[i];
if(dis[k].d>dis[t].d+val[i])
{
dis[k].d=dis[t].d+val[i];
if(!vis[k])
{
lis.push(dis[k]);
}
}
}
}
return;
}
int main()
{
freopen("CF786B.in","r",stdin);
freopen("CF786B.out","w",stdout);
long long i,j,ta,tb,opt,v,u,val;
scanf("%lld%lld%lld",&n,&q,&s);
// read(n);
// read(q);
// read(s);
build(1,1,n,0);
build(1,1,n,n*4);
for(i=1;i<=q;i++)
{
scanf("%lld",&opt);
// read(opt);
if(opt==1)
{
scanf("%lld%lld%lld",&v,&u,&val);
// read(v);
// read(u);
// read(val);
// edge[rleaf[v]].push_back(eddg(lleaf[u],val));
add(rleaf[v],lleaf[u],val);
}
else if(opt==2)
{
scanf("%lld%lld%lld%lld",&v,&ta,&tb,&val);
// read(v);
// read(ta);
// read(tb);
// read(val);
inc(1,ta,tb,0,rleaf[v],val);
}
else
{
scanf("%lld%lld%lld%lld",&v,&ta,&tb,&val);
// read(v);
// read(ta);
// read(tb);
// read(val);
inc(1,ta,tb,n*4,lleaf[v],val);
}
}
dijkstra();
for(i=1;i<=n;i++)
{
if(dis[rleaf[i]].d!=INF)
{
printf("%lld ",dis[rleaf[i]].d);
}
else
{
printf("-1 ");
}
}
return 0;
}
```
by Exp10re @ 2024-02-03 17:53:06
```cpp
dis[i].d=INF;
dis[i].id=i;
dis[i].d=INF;
dis[i].id=i;
```
diji的这里为什么重复两遍
by _WRYYY_ @ 2024-02-03 19:41:10
@[Exp10re](/user/403069) 点相关数组开 $8$ 倍（包括上面没开这么多的 `dis`），边相关数组开 $21$ 倍（总边数为 $2(2n-1-1)+m\log n=4n-4+m\log n$）即可。
by DaShaber @ 2024-02-03 19:44:17
比较建议使用 `std::vector`。
by DaShaber @ 2024-02-03 19:44:56
赞同楼上
[附一个我写的 vector 写法](https://codeforces.com/contest/786/submission/230130435)
by _WRYYY_ @ 2024-02-03 19:49:50
可能会有一点抽象
by _WRYYY_ @ 2024-02-03 19:51:02
@[Exp10re](/user/403069) 能不能帮我看看我的 TLE on #9
```cpp
#include<bits/stdc++.h>
#define int long long
#define int08 508032
#define inf (0x3f3f3f3f3f3f3f3f)
using namespace std;
struct edge{
int v,w;
};
struct tree{
int l,r;
}t[1919810];
vector<edge> e[916414];
int p[114514],n;
void connect(int u,int v,int w)
{
e[u].push_back({v,w});
}
void build(int l,int r,int o)
{
t[o].l=l;t[o].r=r;
if(l==r)
{
p[l]=o;
return;
}
int mid=(l+r)>>1;
build(mid+1,r,o*2+1);
build(l,mid,o*2);
connect(o,o*2,0);
connect(o,o*2+1,0);
connect(o*2+1+int08,o+int08,0);
connect(o*2+int08,o+int08,0);
}
void change(int l,int r,int o,int w,int op,int u)
{
cerr<<o<<endl;
if(l<=t[o].l&&r>=t[o].r)
{
if(op==2) connect(p[u],o,w);
else connect(o+int08,p[u],w);
return;
}
int mid=(t[o].l+t[o].r)/2;
if(r>mid) change(l,r,o*2+1,w,op,u);
if(l<=mid) change(l,r,o*2,w,op,u);
}
priority_queue <pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
int k,dis[1616414],vis[1616414],q,s,i,j,v,l,r,w,op;
void dijkstra(int s)
{
pq.push({0,s});
while(!pq.empty())
{
int du=pq.top().first,u=pq.top().second;
pq.pop();
if(vis[u]) continue;
dis[u]=du;vis[u]=1;
for(auto v:e[u])
{
pq.push({dis[u]+v.w,v.v});
}
}
}
signed main()
{
scanf("%lld%lld%lld",&n,&q,&s);
build(1,n,1);
for(i=1;i<=n;i++)
connect(p[i],p[i]+int08,0),connect(p[i]+int08,p[i],0);
for(j=1;j<=q;j++)
{
scanf("%lld%lld%lld",&op,&v,&l);
if(op>1) scanf("%lld",&r);
scanf("%lld",&w);
if(op>1)
change(l,r,1,w,op,v);
else connect(p[v]+int08,p[l],w);
}
memset(dis,0x3f,sizeof(dis));
dis[p[s]]=0;
dijkstra(p[s]);
for(i=1;i<=n;i++)
cout<<((dis[p[i]]==inf)?(-1):(dis[p[i]]))<<" ";
return 0;
}
```
by int08 @ 2024-02-18 20:21:48
草，我是不是做法假了
by int08 @ 2024-02-18 20:38:35
臭臭臭，是我搞了个 cerr 没删
by int08 @ 2024-02-18 20:47:23
答案是数组开小了。
此贴结。
by Exp10re @ 2024-02-27 09:51:02