数据结构6——线段树优化建图

让我们先从一道题开始。

1、例题

Source

Problem

TimeLimit

MemoryLimit

Codeforces Round #406 (Div. 2)

Legacy

222 seconds

256256256 megabytes

Rick and his co-workers have made a new radioactive formula and a lot of bad guys are after them. So Rick wants to give his legacy to Morty before bad guys catch them.

There are n planets in their universe numbered from 111 to nnn. Rick is in planet number sss (the earth) and he doesn’t know where Morty is. As we all know,Rick owns a portal gun. With this gun he can open one-way portal from a planet he is in to any other planet (including that planet). But there are limits on this gun because he’s still using its free trial.

By default he can not open any portal by this gun. There are qqq plans in the website that sells these guns. Every time you purchase a plan you can only use it once but you can purchase it again if you want to use it more.

Plans on the website have three types:

With a plan of this type you can open a portal from planet vvv to planet u.

With a plan of this type you can open a portal from planet vvv to any planet with index in range [l,?r][l,?r].

With a plan of this type you can open a portal from any planet with index in range [l,?r] to planet vvv.

Rick doesn’t known where Morty is,but Unity is going to inform him and he wants to be prepared for when he finds and start his journey immediately. So for each planet (including earth itself) he wants to know the minimum amount of money he needs to get from earth to that planet.

Input

The first line of input contains three integers n,q and s (1?≤?n,?q?≤?105,1?≤?s?≤?n1?≤?n,?q?≤?10^5,1?≤?s?≤?n) — number of planets,number of plans and index of earth respectively.

The next q lines contain the plans. Each line starts with a number t,type of that plan (1?≤?t?≤?31?≤?t?≤?31?≤?t?≤?3). If t?=?1t?=?1t?=?1 then it is followed by three integers v,uv,u and www where www is the cost of that plan (1?≤?v,?u?≤?n,1?≤?w?≤?1091?≤?v,1?≤?w?≤?10^91?≤?v,1?≤?w?≤?109). Otherwise it is followed by four integers v,l,rv,r and www where w is the cost of that plan (1?≤?v?≤?n,1?≤?l?≤?r?≤?n,1?≤?w?≤?1091?≤?v?≤?n,1?≤?w?≤?10^91?≤?v?≤?n,1?≤?w?≤?109).

Output

In the first and only line of output print n integers separated by spaces. i-th of them should be minimum money to get from earth to i-th planet,or ?-?1 if it’s impossible to get to that planet.

Examples

Input

Output

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

0 28 12

4 3 1

3 4 1 3 12

2 2 3 4 10

1 2 4 16

0 -1 -1 12

Note

In the first sample testcase,Rick can purchase 4th4^text{th}4th plan once and then 2nd2^text{nd}2nd plan in order to get to get to planet number 222.

中文大意

就是给定一张nnn个点的图，求源点sss到每个点的单源最短路。

这张图共有qqq组边，连边方式有333种：

a→ba to ba→b，边权为www的单向边；

a→[l,r]a to[l,r]a→[l,r]，即aaa到连续区间[l,r][l,r]中的每一个点都有一条边权为www的边。

[l,r]→a[l,r]to a[l,r]→a，即连续区间[l,r]中的每一个点都有一条到aaa边权为www的边。

注意数据范围n,q≤105n,q le 10^5n,q≤105。

2、解题思路

如果暴力连边（将一对多或者多对一的连边拆开分别连边），那么最差情况下，我们的边数将达到O(nq)O(nq)O(nq)级别，连边就直接超出能承受的范围——更不要说再跑最短路了。因此我们考虑如何使用一些数据结构把这些一对多的情况压缩成少数的一条边，使每一个连边操作都是O(1)O(1)O(1)的。

注意到所有“一对多”和“多对一“中“多”都是连续区间，回想我们平时处理连续区间的时候，最经常采用的一个数据结构就是线段树了。于是我们把线段树抓两棵过来放在那边。

那我们怎么用线段树呢？

我们在做区间加法的时候，遇到区间问题，我们都是往下查点，直到以这个点为根节点的子树完全包含于我们需要的区间内的时候，直接返回这个点的值——那么我们也可以采用同样的思想：如果我们把线段树的叶节点当做是原图的点，那么对于以这个点为根节点的子树的所有叶节点如果都在范围内，那么我们是不是可以直接在这个子树的根节点的地方连边呢?这样，对于这样一个子区间，我们只需要111条边。至于我们给出的一段区间会被拆成几个小区间，根据线段树的基本知识，我们知道它是常数级别的，因此我们连边就全部变成了O(1)O(1)O(1)的。

慢着，我们刚才说连边连在了线段树的中间，可是原图的点是叶节点，那么我们怎么才能走到中间的那些点呢？

于是我们就只好将每一个点向父节点连边，边权为000。这样就解决问题了？

并没有。因为我们连完边要跑最短路啊，如果我们都向父节点连边，那么中间代表区间的点又应该连向哪里呢?难道连向叶节点吗？这样只能解决多对一的问题，而一对多却不能解决。同样，如果由父节点连向儿子结点，也是不对的。

那么我们就开222棵线段树吧！我们令一颗叫做“入”树（intree），一棵叫做“出”树（outree），其中intree内部从下往上连000权边，outree内部从上往下连边000权边，那么我们对应的连边操作就是：

对于第一种，我们直接将intree对应uuu的叶节点连向outree对应vvv的点。

对于第二种，我们将intree对应aaa的叶节点连向一个或少数几个outree对应的代表区间的结点。

对于第三种，我们将一个或少数几个intree对应的代表区间的结点连向outree对应aaa的叶节点。

特别的，因为我们对于每个点在intree和outree都有直接对应的结点，他们实际上表示的是同一个东西，所以我们在intree和outree的叶节点之间对应的连上无向边。

最后，我们只需要跑一遍从intree的对应sss结点跑一遍到outree对应所有结点的最短路即可。

时间复杂度：O((n+q)log?2n+最短路时间复杂度)O((n+q) log_2 n+最短路时间复杂度)O((n+q)log2?n+最短路时间复杂度)，或者近似看做是O(qlog?2n)O(q log_2 n)O(qlog2?n)。

空间复杂度：O(n)O(n)O(n)。

代码如下：

#include

#include

#include

using namespace std;

#define lson(x) ((x)<<1)

#define rson(x) ((x)<<1|1)

const int MAXN=100010;

const int MAXM=1000010;

long long INF;

struct node{//segment_tree

int id;

int l,r;

}intree[MAXN<<2],outree[MAXN<<2];

struct edge{//graph::edge

int v;

long long w;

edge *nxt;

edge(){

v=w=0;

nxt=NULL;

}

}*head[MAXM];

struct road{//dijkstra

int i;

long long dis;

bool operator<(const road &rhs)const{

return dis>rhs.dis;

}

};

priority_queueq;

int n,m,s;

int innum[MAXN],ounum[MAXN];

long long d[MAXM];

int vis[MAXM],cnt=0;

void adde(int u,int v,long long w){

edge *p=new edge;

p->v=v;p->w=w;

p->nxt=head[u];

head[u]=p;

}

int inbuild(int o,int l,int r){

intree[o].l=l;intree[o].r=r;intree[o].id=cnt++;

if(l==r)

return innum[l]=intree[o].id;

int mid=(l+r)>>1;

adde(inbuild(lson(o),mid),intree[o].id,0);

adde(inbuild(rson(o),mid+1,r),0);

return intree[o].id;

}

int oubuild(int o,int r){

outree[o].l=l;outree[o].r=r;outree[o].id=cnt++;

if(l==r)

return ounum[l]=outree[o].id;

int mid=(l+r)>>1;

adde(outree[o].id,oubuild(lson(o),0);

adde(outree[o].id,oubuild(rson（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!