首页 > 代码库 > 区间->点,点->区间,线段树优化建图+dijstra Codeforces Round #406 (Div. 2) D

区间->点,点->区间,线段树优化建图+dijstra Codeforces Round #406 (Div. 2) D

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] +w,这个符合线段树中的单点更新

对于第二种边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掉即可,因为后续再也用不到这个区间了!

所以这个也是线段树中的单点更新

 

 

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\n")
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\n", 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\n", 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;
}
View Code

 

区间->点,点->区间,线段树优化建图+dijstra Codeforces Round #406 (Div. 2) D