bzoj3694最短路

Description

给出一个n个点m条边的无向图，n个点的编号从1~n，定义源点为1。定义最短路树如下：从源点1经过边集T到任意一点i有且仅有一条路径，且这条路径是整个图1到i的最短路径，边集T构成最短路树。给出最短路树，求对于除了源点1外的每个点i，求最短路，要求不经过给出的最短路树上的1到i的路径的最后一条边。

Input

第一行包含两个数n和m，表示图中有n个点和m条边。
接下来m行，每行有四个数ai，bi，li，ti，表示图中第i条边连接ai和bi权值为li，ti为1表示这条边是最短路树上的边，ti为0表示不是最短路树上的边。
Output

输出n-1个数，第i个数表示从1到i+1的要求的最短路。无法到达输出-1。
Sample Input

5 9
3 1 3 1
1 4 2 1
2 1 6 0
2 3 4 0
5 2 3 0
3 2 2 1
5 3 1 1
3 5 2 0
4 5 4 0
Sample Output

6 7 8 5
HINT

对于100%的数据，n≤4000，m≤100000，1≤li≤100000

solution

我的方法很诡异

首先删一条边相当于把一棵子树孤立出来。

那么答案应要通过其他边绕到子树外面的点，再回到根。

我们记d[i][j]表示以i为根的子树到其他点的最短路。

可以用类似树形dp的方法把儿子的信息合并上来。

O(n^2+m)

其他方法

考虑一条非树边，假设它连接了u，v

那么他可以贡献的段为u~lca，u~lca

树剖维护

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define maxn 4005
#define inf 1e9
using namespace std;
int n,m,t1,t2,t3,t4,head[maxn],tot=1;
int d[maxn][maxn],ans[maxn];
int dfst[maxn],dfsn[maxn],sc,len[maxn],flag[maxn];
struct node{
    int v,nex,w,op;
}e[200005];
void lj(int t1,int t2,int t3,int t4){
    e[++tot].v=t2;e[tot].w=t3;e[tot].op=t4;e[tot].nex=head[t1];head[t1]=tot;
}
void DFS(int k,int fa){
    dfst[k]=++sc;
    for(int i=head[k];i;i=e[i].nex){
        if(!e[i].op||e[i].v==fa)continue;
        len[e[i].v]=len[k]+e[i].w;
        DFS(e[i].v,k);
    }
    dfsn[k]=sc;
}
void dfs(int k,int fa,int b){
    for(int i=head[k];i;i=e[i].nex){
        if(!e[i].op||e[i].v==fa)continue;
        dfs(e[i].v,k,i);
    }
    for(int i=1;i<=n;i++)d[k][i]=inf;
    for(int i=head[k];i;i=e[i].nex){
        if(!e[i].op||e[i].v==fa)continue;
        for(int x=1;x<=n;x++)d[k][x]=min(d[k][x],d[e[i].v][x]+e[i].w);
        flag[e[i].v]=1;
    }//合并子树 
    for(int i=head[k];i;i=e[i].nex){
        if(i==(b^1))continue;
        d[k][e[i].v]=min(d[k][e[i].v],e[i].w);
    }// itself
    int l=dfst[k],r=dfsn[k];
    //cout<<"k: "<<k<<endl;
    ans[k]=inf;
    for(int x=1;x<=n;x++){
        //cout<<d[k][x]<<' ';
        if(dfst[x]<l||dfst[x]>r){
            ans[k]=min(ans[k],d[k][x]+len[x]);
        }
    }//cout<<endl;
    for(int i=head[k];i;i=e[i].nex){
        flag[e[i].v]=0;
    }
}
int main()
{
    freopen("shortest.in","r",stdin);
    freopen("shortest.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d%d",&t1,&t2,&t3,&t4);
        lj(t1,t2,t3,t4);lj(t2,t1,t3,t4);
    }
    DFS(1,0);
    //for(int k=1;k<=n;k++)cout<<k<<' '<<len[k]<<' '<<dfst[k]<<endl;
    dfs(1,0,0);
    if(ans[2]!=inf)printf("%d",ans[2]);
    else printf("-1");
    for(int i=3;i<=n;i++){
        if(ans[i]==inf)printf(" -1");
        else printf(" %d",ans[i]);
    }
    puts("");
    return 0;
}