题意翻译
Rick 和他的同事们做出了一种新的带放射性的婴儿食品(???根据图片和原文的确如此…)，与此同时很多坏人正追赶着他们。因此 Rick 想在坏人们捉到他之前把他的遗产留给 Morty。
在宇宙中一共有 nn 个星球标号为 1 \sim n1∼n。Rick 现在身处于标号为 ss 的星球(地球)但是他不知道 Morty 在哪里。
众所周知，Rick 有一个传送枪，他用这把枪可以制造出一个从他所在的星球通往其他星球(也包括自己所在的星球)的单行道路。但是由于他还在用免费版，因此这把枪的使用是有限制的。
默认情况下他不能用这把枪开启任何传送门。在网络上有 qq 个售卖这些传送枪的使用方案。每一次你想要实施这个方案时你都可以购买它，但是每次购买后只能使用一次。每个方案的购买次数都是无限的。
网络上一共有三种方案可供购买：
开启一扇从星球 vv 到星球 uu 的传送门；
开启一扇从星球 vv 到标号在 [l,r][l,r] 区间范围内任何一个星球的传送门。(即这扇传送门可以从一个星球出发通往多个星球)
开启一扇从标号在 [l,r][l,r] 区间范围内任何一个星球到星球 vv 的传送门。(即这扇传送门可以从多个星球出发到达同一个星球)
Rick 并不知道 Morty 在哪儿，但是 Unity 将要通知他 Morty 的具***置，并且他想要赶快找到通往所有星球的道路各一条并立刻出发。因此对于每一个星球(包括地球本身)他想要知道从地球到那个星球所需的最小钱数。
输入数据：
输入数据的第一行包括三个整数 nn，qq 和 ss 分别表示星球的数目，可供购买的方案数目以及地球的标号。
接下来的 qq 行表示 qq 种方案。
输入 1 v u w 表示第一种方案，其中 v,uv,u 意思同上，ww 表示此方案价格。
输入 2 v l r w 表示第二种方案，其中 v,l,rv,l,r 意思同上，ww 表示此方案价格。
输入 3 v l r w 表示第三种方案，其中 v,l,rv,l,r 意思同上，ww 表示此方案价格。
输出格式：
输出一行用空格隔开的 nn 个整数分别表示从地球到第 ii 个星球所需的最小钱数。
说明： 在第一组测试样例里，Rick 可以先购买第 44 个方案再购买第 22 个方案从而到达标号为 22 的星球.
【数据范围】
对于 100%100% 的数据，1\le n,q \le 10^51≤n,q≤10
5
，1\le w \le 10^91≤w≤10
9
输入输出样例
输入 #1复制
3 5 1
2 3 2 3 17
2 3 2 2 16
2 2 2 3 3
3 3 1 1 12
1 3 3 17
输出 #1复制
0 28 12
输入 #2复制
4 3 1
3 4 1 3 12
2 2 3 4 10
1 2 4 16
输出 #2复制
0 -1 -1 12
什么是线段树优化建图呢？
当有一个点到一个区间，或者一个区间到点这种操作，因为我们不能暴力去连边，所以我们可以利用线段树来优化建图的过程，因为线段树对应了所有区间，但是节点数不多，故我们可以这样优化。
对于这道题，既有点到区间，又有区间到点，所以我们需要两颗线段树。
然后线段树用动态开点最好，因为我们有两颗树。
大概图形：
AC代码：
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10,M=2e6+10;
const int inf=0x3f3f3f3f3f3f3f3f;
int n,m,s,lc[N*20],rc[N*20],rt1,rt2,cnt,d[N<<2],vis[N<<2];
int head[N<<2],nex[M],to[M],w[M],tot;
inline void add(int a,int b,int c){
to[++tot]=b; nex[tot]=head[a]; w[tot]=c; head[a]=tot;
}
void build1(int &p,int l,int r){
if(l==r) return void(p=l);
p=++cnt; int mid=l+r>>1;
build1(lc[p],l,mid); build1(rc[p],mid+1,r);
add(p,lc[p],0); add(p,rc[p],0);
}
void build2(int &p,int l,int r){
if(l==r) return void(p=l);
p=++cnt; int mid=l+r>>1;
build2(lc[p],l,mid); build2(rc[p],mid+1,r);
add(lc[p],p,0); add(rc[p],p,0);
}
void link1(int p,int l,int r,int ql,int qr,int u,int w){
if(l==ql&&r==qr) return void(add(u,p,w));
int mid=l+r>>1;
if(qr<=mid) link1(lc[p],l,mid,ql,qr,u,w);
else if(ql>mid) link1(rc[p],mid+1,r,ql,qr,u,w);
else link1(lc[p],l,mid,ql,mid,u,w),link1(rc[p],mid+1,r,mid+1,qr,u,w);
}
void link2(int p,int l,int r,int ql,int qr,int u,int w){
if(l==ql&&r==qr) return void(add(p,u,w));
int mid=l+r>>1;
if(qr<=mid) link2(lc[p],l,mid,ql,qr,u,w);
else if(ql>mid) link2(rc[p],mid+1,r,ql,qr,u,w);
else link2(lc[p],l,mid,ql,mid,u,w),link2(rc[p],mid+1,r,mid+1,qr,u,w);
}
void dijkstra(int s){
priority_queue<pair<int,int> > q;
memset(d,0x3f,sizeof d); d[s]=0; q.push({0,s});
while(q.size()){
int u=q.top().second; q.pop();
if(vis[u]) continue; vis[u]=1;
for(int i=head[u];i;i=nex[i]){
if(!vis[to[i]]&&d[to[i]]>d[u]+w[i]){
d[to[i]]=d[u]+w[i]; q.push({-d[to[i]],to[i]});
}
}
}
}
signed main(){
cin>>n>>m>>s; cnt=n;
build1(rt1,1,n); build2(rt2,1,n);
while(m--){
int op,v,u,w,l,r; scanf("%lld",&op);
if(op==1) scanf("%lld %lld %lld",&v,&u,&w),add(v,u,w);
else if(op==2){
scanf("%lld %lld %lld %lld",&v,&l,&r,&w);
link1(rt1,1,n,l,r,v,w);
}else{
scanf("%lld %lld %lld %lld",&v,&l,&r,&w);
link2(rt2,1,n,l,r,v,w);
}
}
dijkstra(s);
for(int i=1;i<=n;i++) printf("%lld ",d[i]==inf?-1:d[i]);puts("");
return 0;
}
京公网安备 11010502036488号