题目描述

Description

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

题目分析

先将最短路树建出来 然后枚举非树边 每条非树边能更新两个端点形成的环上的点 并且还要除去两个端点的lca
使用树链剖分QAQ

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
struct wy
{
    int x,y,c,us;
}ed[300100];
int dis[200100];
struct cmp2
{
    bool operator()(const int &a,const int &b)
    {
        return dis[a]>dis[b];
    }
};
struct your
{
    int tot,head[200100],to[400100],net[400100],val[400100],vis[200100];
    void add(int x,int y,int c) { net[++tot]=head[x],head[x]=tot,to[tot]=y,val[tot]=c; }
    void spfa()
    {   
        priority_queue<int,vector<int>,cmp2>q;
        memset(dis,0x3f,sizeof dis);
        q.push(1),dis[1]=0;
        while(q.size())
        {
            int x=q.top();
            q.pop(),vis[x]=0;
            for(int i=head[x];i;i=net[i])
                if(dis[to[i]]>dis[x]+val[i])
                {
                    dis[to[i]]=dis[x]+val[i];
                    if(!vis[to[i]]) vis[to[i]]=1,q.push(to[i]);
                }
        }
    }
}A;
bool cmp(int j,int k) { return ed[j].c>ed[k].c; }
struct my 
{
    int tot,head[200100],to[400100],net[400100],val[400100],cnt;
    void add(int x,int y,int c) { net[++tot]=head[x],head[x]=tot,to[tot]=y,val[tot]=c;}
    int deep[200100],fa[200100],top[200100],size[200100],son[200100],dis[200100],number[200100];
    void dfs(int x)
    {
        deep[x]=deep[fa[x]]+1,size[x]=1;
        for(int i=head[x];i;i=net[i])
        {
            if(to[i]==fa[x]) continue;
            dis[to[i]]=dis[x]+val[i],fa[to[i]]=x,dfs(to[i]),size[x]+=size[to[i]];
            if(size[son[x]]<size[to[i]]) son[x]=to[i];
        }
    }
    void dfs2(int x,int temp)
    {
        top[x]=temp,number[x]=++cnt;
        if(son[x]) dfs2(son[x],temp);
        for(int i=head[x];i;i=net[i])
            if(to[i]!=fa[x]&&to[i]!=son[x]) dfs2(to[i],to[i]);
    }
    struct seg
    {
        int x,y,sum,add;
    }a[500100];
    void build(int dx,int dy,int num)
    {
        a[num].x=dx,a[num].y=dy;
        if(dx==dy) { a[num].sum=0x7f7f7f7f; return ; }
        int mid=(dx+dy)>>1;
        build(dx,mid,num<<1),build(mid+1,dy,num<<1|1);
    }
    void up(int num,int c) { a[num].sum=a[num].add=c; }
    void pushdown(int num) { up(num<<1,a[num].add),up(num<<1|1,a[num].add),a[num].add=0; }
    void update(int dx,int dy,int c,int num)
    {
        if(dx==a[num].x&&dy==a[num].y) { up(num,c); return ; }
        if(a[num].add) pushdown(num);
        int mid=(a[num].x+a[num].y)>>1;
        if(dy<=mid) update(dx,dy,c,num<<1);
        else if(dx>mid) update(dx,dy,c,num<<1|1);
        else update(dx,mid,c,num<<1),update(mid+1,dy,c,num<<1|1);
    }
    int ask(int dx,int num)
    {
        if(a[num].x==dx&&a[num].y==dx) return a[num].sum;
        if(a[num].add) pushdown(num);
        int mid=(a[num].x+a[num].y)>>1;
        if(dx<=mid) return ask(dx,num<<1);
        else return ask(dx,num<<1|1);
    }
    void change(int x,int y,int c)
    {
        while(top[x]!=top[y]) 
        {
            if(deep[top[x]]<deep[top[y]]) swap(x,y);
            update(number[top[x]],number[x],c,1);
            x=fa[top[x]];
        }
        if(x==y) return ;
        if(deep[x]>deep[y]) swap(x,y);
        update(number[x]+1,number[y],c,1);
    }
    int lca(int x,int y)
    {
        while(top[x]!=top[y])
        {
            if(deep[top[x]]<deep[top[y]]) swap(x,y);
            x=fa[top[x]];
        }
        return deep[x]>deep[y]?y:x;
    }
    int st[300100];
    void work()
    {
        dfs(1),dfs2(1,1),build(1,n,1);
        for(int i=1;i<=m;i++)
            if(!ed[i].us) ed[i].c+=dis[ed[i].x]+dis[ed[i].y],st[++st[0]]=i;
        sort(st+1,st+st[0]+1,cmp);
        for(int l,i=1;i<=st[0];i++) 
        {
            l=lca(ed[st[i]].x,ed[st[i]].y);
            change(l,ed[st[i]].x,ed[st[i]].c);
            change(l,ed[st[i]].y,ed[st[i]].c);
        }
        for(int i=2;i<=n;i++)
        {
            int tmp=ask(number[i],1);
            if(tmp==0x7f7f7f7f) printf("-1\n");
            else printf("%d\n",tmp-dis[i]);
        }
    }
}B;
int main()
{   
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&ed[i].x,&ed[i].y,&ed[i].c),A.add(ed[i].x,ed[i].y,ed[i].c),A.add(ed[i].y,ed[i].x,ed[i].c);
    A.spfa();
    for(int i=1;i<=m;i++)
    {
        if(dis[ed[i].x]==dis[ed[i].y]+ed[i].c) ed[i].us=1,B.add(ed[i].y,ed[i].x,ed[i].c);
        else if(dis[ed[i].y]==dis[ed[i].x]+ed[i].c) ed[i].us=1,B.add(ed[i].x,ed[i].y,ed[i].c);
    }
    B.work();
    return 0;
}