一.题目链接：

CodeForces-787D

二.题目大意：

有 n 个点，q 个关系，从起点 s 出发，求单源最短路.

其中，关系有三种：

①：u v c 表明 u 到 v 有一条花费为 c 的路.

②：u l r c 表明 u 到区间 [l, r] 内任意一点有一条花费为 c 的路.

③：u l r c 表明区间 [l, r] 内任意一点到 u 有一条花费为 c 的路.

三.分析：

直接暴力的话，边数太多，spfa 会炸掉.

由于涉及到区间操作，不妨利用线段树建图，之后再spfa即可.

线段树建图需建两棵树 -- 出度树 和 入度树.

如图所示：

四.代码实现：

#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-6
#define pi acos(-1.0)
#define ll long long int
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
const int M = (int)1e5;
const ll inf = 0x3f3f3f3f3f;

struct tree
{
    int l;
    int r;
    int id;
}in_tree[M * 4 + 5], out_tree[M * 4 + 5];

struct Edge
{
    int u;
    int v;
    ll c;
    int next;
}Edge[M * 20 + 5];

int cnt, num;
ll dis[M * 8 + 5];
int head[M * 8 + 5];
bool vis[M * 8 + 5];
int in_id[M + 5];
int out_id[M + 5];

struct cmp
{
    bool operator()(int a, int b)
    {
        return dis[a] > dis[b];
    }
};

void init(int n)
{
    cnt = num = 0;
    num = 1;
    for(int i = 1; i <= n; ++i)
    {
        vis[i] = 0;
        head[i] = -1;
        dis[i] = inf;
    }
}

void add(int u, int v, ll c)
{
    Edge[cnt].u = u;
    Edge[cnt].v = v;
    Edge[cnt].c = c;
    Edge[cnt].next = head[u];
    head[u] = cnt++;
}

void build_out(int k, int l, int r)
{
    out_tree[k].l = l;
    out_tree[k].r = r;
    out_tree[k].id = num++;
    if(l == r)
    {
        out_id[l] = out_tree[k].id;
        return;
    }
    int mid = (l + r) / 2;
    build_out(k * 2, l, mid);
    build_out(k * 2 + 1, mid + 1, r);
    add(out_tree[k * 2].id, out_tree[k].id, 0);
    add(out_tree[k * 2 + 1].id, out_tree[k].id, 0);
}

void build_in(int k, int l, int r)
{
    in_tree[k].l = l;
    in_tree[k].r = r;
    in_tree[k].id = num++;
    if(l == r)
    {
        in_id[l] = in_tree[k].id;
        add(in_id[l], out_id[l], 0);
        return;
    }
    int mid = (l + r) / 2;
    build_in(k * 2, l, mid);
    build_in(k * 2 + 1, mid + 1, r);
    add(in_tree[k].id, in_tree[k * 2].id, 0);
    add(in_tree[k].id, in_tree[k * 2 + 1].id, 0);
}

void update1(int k, int u, int l, int r, ll c)
{
    if(in_tree[k].l >= l && in_tree[k].r <= r)
    {
        add(out_id[u], in_tree[k].id, c);
        return;
    }
    int mid = (in_tree[k].l + in_tree[k].r) / 2;
    if(l <= mid)
        update1(k * 2, u, l, r, c);
    if(mid < r)
        update1(k * 2 + 1, u, l, r, c);
}

void update2(int k, int l, int r, int v, ll c)
{
    if(out_tree[k].l >= l && out_tree[k].r <= r)
    {
        add(out_tree[k].id, in_id[v], c);
        return;
    }
    int mid = (out_tree[k].l + out_tree[k].r) / 2;
    if(l <= mid)
        update2(k * 2, l, r, v, c);
    if(mid < r)
        update2(k * 2 + 1, l, r, v, c);
}

void spfa(int start)
{
    vis[start] = 0;
    dis[start] = 0;
    priority_queue <int, vector<int>, cmp> q;
    q.push(start);
    while(!q.empty())
    {
        int u = q.top();
        q.pop();
        vis[u] = 0;
        for(int i = head[u]; ~i; i = Edge[i].next)
        {
            int v = Edge[i].v;
            if(dis[v] > dis[u] + Edge[i].c)
            {
                dis[v] = dis[u] + Edge[i].c;
                if(!vis[v])
                {
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
}

int main()
{
    int n, q, s;
    scanf("%d %d %d", &n, &q, &s);
    init(n * 8);
    build_out(1, 1, n);
    build_in(1, 1, n);
    int t;
    int u, v, l, r;
    ll c;
    while((q--) > 0)
    {
        scanf("%d", &t);
        if(t == 1)
        {
            scanf("%d %d %lld", &u, &v, &c);
            add(out_id[u], in_id[v], c);
        }
        else if(t == 2)
        {
            scanf("%d %d %d %lld", &u, &l, &r, &c);
            update1(1, u, l, r, c);
        }
        else if(t == 3)
        {
            scanf("%d %d %d %lld", &v, &l, &r, &c);
            update2(1, l, r, v, c);
        }
    }
    spfa(out_id[s]);
    for(int i = 1; i <= n; ++i)
        printf("%lld%c", dis[out_id[i]] == inf ? -1 : dis[out_id[i]], i == n ? '\n' : ' ');
    return 0;
}