一道最短路建模

题目链接:http://codeforces.com/contest/787/problem/D
需要用上线段树，我用的是zkw，
注意边的数量是nlogn的
题解:

• 存在一些边是点到一个连续区间的。
• 如果把点到区间的边都看成挨个挨个连，边的数量会非常大会超时
• 如果设立些辅助点和辅助边，辅助边的值为0，点到区间的边步直接连在点上，而是连到辅助点上。可以做到把一个区间边的数量由O(n)级降到O(log(n))级的。
  代码(除了zkw其他都是自己写的)

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
const int MAXN = 1<<18;
const int DBG = 0;
struct Edge{
    int to;
    ll d;
    Edge* next;
}*head[MAXN*2], e[MAXN*10];
bool vis[MAXN*2];
ll dis[MAXN*2];
int ne, n, q, s, M;
int getB(int x) {
    int ret = 1;
    while(ret<x) ret<<=1;
    return ret;
}
inline void addedge(int fr, int to, int d) {
    e[ne] = (Edge){to, d, head[fr]};
    head[fr] = e+ne++;
}
void addinterval(int u, int l, int r, int w, int t) {
    for(l=l+M-1, r=r+M+1, u=u|M; l^r^1; l>>=1, r>>=1) {
        if(~l&1) {
            if(t==2) addedge(u, l^1, w);
            else addedge((l^1)|MAXN, u, w);
        }
        if(r&1) {
            if(t==2) addedge(u, r^1, w);
            else addedge((r^1)|MAXN, u, w);
        }
    }
}
void Dijkstra(int s) {
    memset(dis, 0x3f, sizeof(dis));
    priority_queue<pair<ll, int> > pq;
    dis[s] = 0;
    pq.push(make_pair(0ll,s));
    while(pq.size()) {
        pair<ll, int> pu = pq.top();
        pq.pop();
        int u=pu.second;
        if(vis[u]) continue;
        vis[u] = true;
        if(DBG) printf("sel %d\n", u);
        for(Edge* p=head[u]; p; p=p->next) {
            if(dis[p->to]>dis[u]+p->d) {
                dis[p->to] = dis[u]+p->d;
                pq.push(make_pair(-dis[p->to], p->to));
            }
        }
    }
}
int main() {
    scanf("%d%d%d", &n, &q, &s);
    M = getB(n+2);
    for(int i=1; i<M; ++i) {
        addedge(i, i<<1, 0);
        addedge(i, i<<1|1, 0);
        addedge(i<<1|MAXN, i|MAXN, 0);
        addedge(i<<1|1|MAXN, i|MAXN, 0);
    }
    for(int i=0; i<M; ++i) {
        addedge(i|M, i|M|MAXN, 0);
        addedge(i|M|MAXN, i|M, 0);
    }
    while(q--) {
        int t, v, l, r, w;
        scanf("%d%d", &t, &v);
        if(t==1) {
            scanf("%d%d", &l, &w);
            addedge(M|v, M|l, w);
        }
        else {
            scanf("%d%d%d", &l, &r, &w);
            addinterval(v, l, r, w, t);
        }
    }
    Dijkstra(s|M);
    for(int i=1; i<n+1; ++i)
        printf("%I64d%c", vis[M|i]?dis[M|i]:-1ll, i==n?'\n':' ');
    return 0;
}