http://codeforces.com/contest/787/problem/D
题目大意：有n个点，三种有向边，这三种有向边一共加在一起有m个，然后起点是s，问，从s到所有点的最短路是多少？
第一种边：u->v w 表示节点u到v有连接一条有向边，权值为w
第二种边：u->[l,r] w 表示节点u到区间[l,r]连接一条有向边，权值为w
第三种边：[l,r]->u w 表示区间[l, r]所有的节点到u都有一条有向边，权值为w
思路：
我们知道，对于dijstra都是用priority_queue来优化的，这样才保证了每个节点值访问一次的复杂度。
算法一：
对于第二种边和第三种边分别对[l,r]->u的这些点进行建图，再跑dij。但是最坏情况的建图是O(n*n)，所以肯定会TLE
从算法一中看出，这道题的瓶颈在于如何处理区间和点之间的边的关系。
我们仔细的分析一下dijstra以后发现，每个节点的访问次数只有1，也就是说，优先队列里面取出来的点，取出来以后就不可能有比他更小的点了，而且这个点只会访问一次。
对于第一种边，u->v，那么很明显就是d[v] = d[u] +ｗ，这个符合线段树中的单点更新
对于第二种边u->[l,r]，那么也就是说，从u出发，到区间[l,r]所有的节点的val都修改为d[u] + w，这个符合线段树中的成段更新
对于第三种边[l,r]->u来说
从[l,r]出发->u的路径可以有无数条，那么如何做才能保证d[u]是从区间[l,r]里面得来的最小的呢？
根据priority_queue，那么我们最先访问过的点，就是必然是权值最小的，那么也就是说，假设当前我们访问到节点x，那么x属于区间[l,r]中，那么x一定是区间[l,r]中权值最小的，所以我们只需要利用这个d[x]去更新即可，即d[u] = d[x] + w。当然，如果这个[l,r]区间使用过了，就不需要再使用了，pop掉即可，因为后续再也用不到这个区间了！
所以这个也是线段树中的单点更新
第一次知道vector可以pop_ back
que就是priority_queue，tree保存目前节点能往右延伸到的最大值。
然后对一个值从队列里面访问过了，那么就不需要再次访问了
//看看会不会爆int!数组会不会少了一维！ //取物问题一定要小心先手胜利的条件 #include <bits/stdc++.h> using namespace std; #pragma comment(linker,"/STACK:102400000,102400000") #define LL long long #define ALL(a) a.begin(), a.end() #define pb push_back #define mk make_pair #define fi first #define se second #define haha printf("haha ") const int maxn = 1e5 + 5; const LL inf = 1e16; int n, q, s; vector<pair<int, LL> > one[maxn]; vector<pair<pair<int, int>, LL> > er[maxn], san[maxn]; ///tree保存目前节点能往右边延伸到的最右端，que保存目前节点的最小值 int tree[maxn << 2]; pair<LL, int> que[maxn << 2]; LL lazy[maxn << 2]; LL d[maxn]; inline void update_queue(int o, LL val){ if (que[o].fi == inf + 1) return; que[o].fi = min(que[o].fi, val); if (lazy[o] == -1) lazy[o] = val; lazy[o] = min(lazy[o], val); } void push_down(int o){ int lb = o << 1, rb = o << 1 | 1; if (lazy[o] != -1){ update_queue(lb, lazy[o]); update_queue(rb, lazy[o]); lazy[o] = -1; } } /* 因为对于第二种情况：v->[l,r]来说，[l,r]的值是相同的，所以我们就假定按照优先级来计算即可 对于第三种情况：[l, r]->v来说，[l,r]中只能是最小的那个点到v，因为只有这样才能保证最短 */ void update(int ql, int qr, int l, int r, int o, LL val){ //printf("ql = %d qr = %d l = %d r = %d ", ql, qr, l, r); if (ql <= l && qr >= r){ if (val == inf + 1) que[o] = mk(val, l); else update_queue(o, val); return ; } push_down(o); int mid = (l + r) / 2; if (ql <= mid) update(ql, qr, l, mid, o << 1, val); if (qr > mid) update(ql, qr, mid + 1, r, o << 1 | 1, val); que[o] = min(que[o << 1], que[o << 1 | 1]); // printf("que[%d] = %lld %d val = %lld ", o, que[o], val); } vector<pair<int, LL> > ve; void find_point(int x, int l, int r, int o){ if (l > x || tree[o] < x) return ; if (l == r){ while (!san[l].empty() && san[l].back().fi.fi >= x){ ve.push_back(mk(san[l].back().fi.se, san[l].back().se)); san[l].pop_back(); } tree[o] = -1; if (!san[l].empty()) tree[o] = san[l].back().fi.fi; return ; } int mid = (l + r) / 2; find_point(x, l, mid, o << 1); find_point(x, mid + 1, r, o << 1 | 1); tree[o] = max(tree[o << 1], tree[o << 1 | 1]); } void solve(){ for (int i = 1; i <= n; i++) d[i] = inf; update(s, s, 1, n, 1, 0);///更新初始点 while (true){ int u = que[1].se; LL cost = que[1].fi; if (cost == inf + 1) break; d[u] = min(cost, d[u]); update(u, u, 1, n, 1, inf + 1);///如果从队列里面访问过了，就不需要再访问了 ///第一种，单点更新u->v for (int i = 0; i < one[u].size(); i++){ int v = one[u][i].fi; LL w = one[u][i].se; update(v, v, 1, n, 1, d[u] + w); } ///第二种，成段更新，u->[l,r] for (int i = 0; i < er[u].size(); i++){ int ql = er[u][i].fi.fi, qr = er[u][i].fi.se; LL w = er[u][i].se; update(ql, qr, 1, n, 1, d[u] + w); } ///第三种，单点更新，[l, r]->v，其中[l,r]包含了u节点 ve.clear(); find_point(u, 1, n, 1); for (int i = 0; i < ve.size(); i++){ int v = ve[i].fi; LL w = ve[i].se; update(v, v, 1, n, 1, d[u] + w); } } for (int i = 1; i <= n; i++){ if (d[i] == inf) printf("-1 "); else printf("%lld ", d[i]); } cout << endl; } void build(int l, int r, int o){ if (l == r){ que[o] = mk(inf, l); tree[o] = -1; if (!san[l].empty()) tree[o] = san[l].back().fi.fi; return ; } int mid = (l + r) / 2; if (l <= mid) build(l, mid, o << 1); if (r > mid) build(mid + 1, r, o << 1 | 1); tree[o] = max(tree[o << 1], tree[o << 1 | 1]); que[o] = min(que[o << 1], que[o << 1 | 1]); } int main(){ cin >> n >> q >> s; for (int i = 1; i <= q; i++){ int ty; scanf("%d", &ty); if (ty == 1){ int u, v; LL val; scanf("%d%d%lld", &u, &v, &val); one[u].pb(mk(v, val)); } else { int u, l, r; LL val; scanf("%d%d%d%lld", &u, &l, &r, &val); if (ty == 2) er[u].pb(mk(mk(l, r), val)); else san[l].pb(mk(mk(r, u), val)); } } for (int i = 1; i <= n; i++) sort(ALL(san[i])); memset(lazy, -1, sizeof(lazy)); build(1, n, 1); solve(); return 0; }