嘟嘟嘟
省选Day1T2不仅考了字符串，还考了线段树优化建图。当时不会，现在赶快学一下。
线段树能优化的图就是像这道题一样，一个点像一个区间的点连边，或一个区间像一个点连边。一个个连就是(O(n ^ 2))复杂度了，当然承受不起。于是就有了线段树了。
原理很简单，就是把一个连续区间的点合并成线段树上的一个点，这样最多有(nlogn)个点。但仅仅这样还不对，所以我们要建两棵树，一个是入度树，一个是出度树。
对于入度树，每一个点要像左右儿子连边，因为如果这个有人像这个点所代表的区间连边，那么也一定能进入他的左右子区间。
对于出度树，左右儿子向父亲连边，因为如果这个点所代表的区间能走到一个点，则他的父亲也一定能到那个点。
而这种连边反过来就不行。
这样我们线段树内部的连边就搞完了，接下来考虑题中的加边。
对于一个点(v)向一个区间连边，就在入度树上区间修改，如果到了递归边界，就从(v)向这个点的编号连边；对于区间向点连边同理，这里就不说了。
上面提到点的编号，有一个很好的方法就是线段树的节点从(n + 1)开始编号，这样原图上的点的编号不会被打乱，点对点的加边还可以正常加。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
typedef long long ll;
typedef double db;
const ll INF = 1e18;
const db eps = 1e-8;
const int maxn = 5e6 + 5;
const int maxe = 1e7 + 5;
inline ll read()
{
ll ans = 0;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) last = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
int n, m, s;
struct Edge
{
int nxt, to, w;
}e[maxe];
int head[maxn], ecnt = -1;
In void addEdge(int x, int y, int w)
{
e[++ecnt] = (Edge){head[x], y, w};
head[x] = ecnt;
}
int tIn[maxn], tOut[maxn], l[maxn], r[maxn], tcnt = 0;
In void build(int now, int L, int R)
{
l[now] = L; r[now] = R;
if(L == R)
{
tIn[now] = tOut[now] = L;
return;
}
tIn[now] = ++tcnt; tOut[now] = ++tcnt;
int mid = (L + R) >> 1;
build(now << 1, L, mid);
build(now << 1 | 1, mid + 1, R);
addEdge(tIn[now], tIn[now << 1], 0);
addEdge(tIn[now], tIn[now << 1 | 1], 0);
addEdge(tOut[now << 1], tOut[now], 0);
addEdge(tOut[now << 1 | 1], tOut[now], 0);
}
In void update(int now, int L, int R, int x, int w, bool flg)
{
if(l[now] == L && r[now] == R)
{
if(flg) addEdge(x, tIn[now], w);
else addEdge(tOut[now], x, w);
return;
}
int mid = (l[now] + r[now]) >> 1;
if(R <= mid) update(now << 1, L, R, x, w, flg);
else if(L > mid) update(now << 1 | 1, L, R, x, w, flg);
else update(now << 1, L, mid, x, w, flg), update(now << 1 | 1, mid + 1, R, x, w, flg);
}
#define pr pair<ll, int>
#define mp make_pair
bool in[maxn];
ll dis[maxn];
In void dijkstra(int s)
{
fill(dis + 1, dis + tcnt + 1, INF); dis[s] = 0;
priority_queue<pr, vector<pr>, greater<pr> > q;
q.push(mp(dis[s], s));
while(!q.empty())
{
int now = q.top().second; q.pop();
if(in[now]) continue;
in[now] = 1;
for(int i = head[now], v; ~i; i = e[i].nxt)
{
if(dis[v = e[i].to] > dis[now] + e[i].w)
{
dis[v] = dis[now] + e[i].w;
q.push(mp(dis[v], v));
}
}
}
}
int main()
{
Mem(head, -1);
n = read(), m = read(), s = read();
tcnt = n; build(1, 1, n);
for(int i = 1; i <= m; ++i)
{
int op = read(), x = read();
if(op == 1)
{
int y = read(), w = read();
addEdge(x, y, w);
}
else
{
int L = read(), R = read(), w = read();
update(1, L, R, x, w, op == 2);
}
}
dijkstra(s);
for(int i = 1; i <= n; ++i) write(dis[i] == INF ? -1 : dis[i]), space; enter;
return 0;
}