Safe Travel
Time Limit: 20000 ms Memory Limit: 65536 KB

Description
Gremlins最近在农场上泛滥,它们经常会阻止牛们从农庄(牛棚_1)走到别的牛棚(牛_i的目的地是牛棚_i).每一个gremlin只认识牛_i并且知道牛_i一般走到牛棚_i的最短路经.所以它们在牛_i到牛棚_i之前的最后一条牛路上等牛_i. 当然,牛不愿意遇到Gremlins,所以准备找一条稍微不同的路经从牛棚_1走到牛棚_i.所以,请你为每一头牛_i找出避免gremlin_i的最短路经的长度.
和以往一样, 农场上的M (2 <= M <= 200,000)条双向牛路编号为1..M并且能让所有牛到达它们的目的地, N(3 <= N <= 100,000)个编号为1..N的牛棚.牛路i连接牛棚a_i(1 <= a_i <= N)和b_i (1 <= b_i <= N)并且需要时间t_i (1 <=t_i <= 1,000)通过.没有两条牛路连接同样的牛棚,所有牛路满足a_i!=b_i.在所有数据中,牛_i使用的牛棚_1到牛棚_i的最短路经是唯一的.
以下是一个牛棚,牛路和时间的例子:

Input
* 第一行: 两个空格分开的数, N和M
* 第2..M+1行: 三个空格分开的数a_i, b_i,和t_i

Output
* 第1..N-1行: 第i行包含一个数:从牛棚_1到牛棚_i+1并且避免从牛棚1到牛棚i+1最短路经上最后一条牛路的最少的时间.如果这样的路经不存在,输出-1.

Sample Input
4 5
1 2 2
1 3 2
3 4 4
3 2 1
2 4 3

Sample Output
3
3
6

由于题目说了1到没个点的最短路是唯一的。那么这些最短路组成的一棵树-Shortest Path Tree也是唯一的。

dijkstra+heap跑一遍。处理出dist数组。建好SPT。树根当然是1。

对于一个结点u。它的父亲设为p。那么根据题意，从1到u的次短路不能经过<p,u>这条边。

①先沿着SPT的边从1走到v。然后通过一条不是SPT的边，走到u本身。

②先沿着SPT的边从1走到v。然后通过一条不是SPT的边，走到u在SPT中的子孙，再沿着SPT上的边就可以走到u了。

考虑给每个节点挂一个可并堆。（二项堆写起来略烦，还是学习了左偏树）

先解决叶子节点u。

叶子节点肯定是上述的第①种情况。

那么把u出发的不是SPT的边<v,u,w>放入一个小根堆中。那么Ans[u]=min{dist[v]+w}。就是堆顶元素。

然后处理非叶子节点u'。

同样，把u'出发的不是SPT的边<v,u',w>放入一个小根堆中。

因为有情况②的存在，所以节点u'的堆要和它所有的儿子v'的堆合并。v'堆合并时要先加上<v',u'>的边权。然后再取出最大值。

为了方便起见，处理节点u时，添加非SPT中的边时，可以把key设为dist[v]+w(v,u)+dist[u]。

如果到了处理u'时取出这个答案的话，Ans[u']=key-dist[u']。（dist[u]-dist[u']就是上述的加上的边权，这样就不用每次合并的时候逐一加了）

还有就是要注意。如果堆顶选出来的这条非SPT边<u,v>，LCA(u,v)在是当前节点的祖先。那就不可行了。这样必定要经过<p,u>边。不合题意。所以不停地删，直到堆顶元素符合。

左偏树中删除堆顶节点的简单办法就是Merge(rt.l,rt.r)了~

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn = 110000,maxm = 510000,inf = 1061109657;
struct node{
    int x,dis;
    node(){};
    node(int _x,int _d):x(_x),dis(_d){};
    inline bool operator < (node b)const{
        return dis < b.dis;
    }
}H[maxn];
int pos[maxn]={0},rt[maxm],An[maxn],dfn[maxn],path[maxn],size = 0,ee = 0,cnt = 0;
int h[maxn],p[maxm],w[maxm],n1[maxm],d[maxn],vis[maxn],D[maxn],tot = 0,n,m;
struct lt{
    int l,r,d,id;
}L[maxm];
inline void sw(int a,int b){
    pos[H[a].x] = b;
    pos[H[b].x] = a;
    swap(H[a],H[b]);
}
#define pt (x >> 1)
#define ls (x << 1)
#define rs (x << 1 | 1)
void up(int x){
    if(x == 1)  return;
    if(H[x] < H[pt])    sw(x,pt),up(pt);
}
void down(int x){
    int s = x;
    if(ls <= size && H[ls] < H[x])  s = ls;
    if(rs <= size && H[rs] < H[s])  s = rs;
    if(s != x)  sw(x,s),down(s);
}
void del(int x){
    sw(x,size);
    size --;
    up(x);
    down(x);
}
void ins(node a){
    H[++ size] = a;
    pos[a.x] = size;
    up(size);
}
void dijkstra(int s){
    size = d[s] = 0;
    ins(node(s,0));
    while(size){
        node u = H[1];
        pos[H[1].x] = 0;
        del(1);
        if(vis[u.x])    continue;
        vis[u.x] = 1;
        for(int i = h[u.x];~i;i = n1[i])    if(!vis[p[i]])
            if(u.dis + w[i] < d[p[i]]){
                d[p[i]] = u.dis + w[i];
                path[p[i]] = u.x;
                if(pos[p[i]]){
                    H[pos[p[i]]].dis = d[p[i]];
                    up(pos[p[i]]);
                }else   ins(node(p[i],d[p[i]]));
            }
    }
}
inline void ae(int a,int b,int c){
    p[ee] = b;  w[ee] = c;  n1[ee] = h[a];  h[a] = ee ++;
    p[ee] = a;  w[ee] = c;  n1[ee] = h[b];  h[b] = ee ++;
}
int merge(int a,int b){
    if(!a || !b)    return max(a,b);
    if(L[a].d > L[b].d) swap(a,b);
    L[a].r = merge(L[a].r,b);
    if(D[L[a].r] > D[L[a].l])   swap(L[a].l,L[a].r);
    if(L[a].r == 0) D[a] = 0;
    else     D[a] = D[L[a].r] + 1;
    return a;
}
void dfs(int u,int fa){
    dfn[u] = ++ tot;
    for(int i = h[u]; ~i;i = n1[i]){
        if(p[i] == fa)  continue;
        if(path[p[i]] == u){
            dfs(p[i],u);
            rt[u] = merge(rt[u],rt[p[i]]);
        }
    }
    for(int i = h[u]; ~i;i = n1[i]){
        if(p[i] == fa)  continue;
        if(path[p[i]] != u){
            L[++ cnt] = (lt){0,0,d[u]+w[i]+d[p[i]],p[i]};
            rt[u] = merge(rt[u],cnt);
        }
    }
    while(rt[u] && dfn[L[rt[u]].id] >= dfn[u])
        rt[u] = merge(L[rt[u]].l,L[rt[u]].r);
    An[u] = rt[u] ? L[rt[u]].d - d[u] : -1;
}
    
int main(){
    memset(h,0xff,sizeof(h));
    scanf("%d%d",&n,&m);
    int u,v,w;
    for(int i = 1;i <= m;i ++){
        scanf("%d%d%d",&u,&v,&w);
        ae(u,v,w);
    }
    memset(d,63,sizeof(d));
    dijkstra(1);
    dfs(1,0);
    for(int i = 2;i <= n;i ++)  printf("%d\n",An[i]);
    return 0;
}

• 相关文章