USACO09JAN安全出行SafeTravel

发表于

洛谷2934 BZOJ3411

  • 题意
    有$n (1 \le n \le 100000)$个点，$m (1 \le m \le 200000)$条边的无向图，点1为起点。求到达每个点不走原最短路径上最后一条边时的最短距离。保证最短路唯一。

  • Solution

    • 刚看到这道题的时候不会做，搜了题解，写了个好巧妙的树链剖分。后来发现竟然还有dfs做法，左偏树做法。
    • 我也太垃圾了吧。

  • 上面是废话。下面进入正题。

    • 由于题目保证最短路唯一，所以跑完最短路之后得到的是一个最短路树而不是DAG。当最短路树上到这个点的最后那条边被截断后，就u要经过至少一条不在最短路树上的边。
    • 一一考虑其他的每条边。
    • 设当前考虑不在最短路树上的边<u,v>，设$x=LCA(u,v)$。那么对于路径P<v,x>(不包括x)上的任意点$t$，都可以更新：$dis2[t] = min(dis2[t], dis[u]+w[u,v]+dis[v]-dis[t])$。路径P<u,x>类似。
    • 可以发现$dis[u] + w[u,v] + dis[v]$是一个定值，树剖维护即可。
  • tips
    • 看来我对稍复杂一点的结构运用还不够。
    • spfa好写，但是小心TLE。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include <bits/stdc++.h>
using namespace std ;
const int maxn = 1e5+5, maxm = 4e5+5, zhf = 0x3f3f3f3f ;
inline void Read ( int &x, char c = getchar() ) {
	for ( x = 0 ; !isdigit(c) ; c = getchar() ) ;
	for ( ; isdigit(c) ; c = getchar() ) x = 10*x + c - '0' ;
}
int n, m, dis[maxn] ;
int e = 1, Begin[maxn], Next[maxm], To[maxm], W[maxm], from[maxm] ;
int ee = 1, be[maxn], nxt[maxn<<1], to[maxn<<1], w[maxn<<1] ;
bool vis[maxn] ;
inline void ADD ( int x, int y, int z ) {
	to[++ee] = y ;
	nxt[ee] = be[x] ;
	be[x] = ee ;
	w[ee] = z ;
}
struct node {
	int x, dis ;
	friend bool operator < ( node a, node b ) { return a.dis > b.dis ; }
} ;
priority_queue <node> Q ;
inline void Dijkstra ( int x ) {
	int i, u ;
	memset ( dis, zhf, sizeof dis ) ;
	Q.push((node){1, 0}) ;
	dis[x] = 0 ;
	node tmp ;
	while ( !Q.empty() ) {
		tmp = Q.top() ;
		Q.pop() ;
		x = tmp.x ; 
		if ( vis[x] ) continue ;
		vis[x] = 1 ;
		for ( i = Begin[x] ; i ; i = Next[i] ) {
			u = To[i] ;
			if ( dis[u] > dis[x] + W[i] ) {
				dis[u] = dis[x] + W[i] ;
				from[u] = i ;
				Q.push((node){u, dis[u]}) ;
			}
		}
	}
}
void add ( int x, int y, int z ) {
	To[++e] = y ;
	Next[e] = Begin[x] ;
	Begin[x] = e ;
	W[e] = z ;
}
bool mark[maxm] ;
int size[maxn], dep[maxn], fa[maxn], son[maxn], top[maxn], dfn[maxn], clk ;
inline int dfs1 ( int x ) {
	size[x] = 1 ;    
	register int i, u ;
	for ( i = be[x] ; i ; i = nxt[i] ) {
		u = to[i] ;
		if ( u == fa[x] ) continue ;
		fa[u] = x ;
		dep[u] = dep[x]+1 ;
        size[x] += dfs1(u) ;
        if ( !son[x] || size[u] > size[son[x]] ) son[x] = u ;
    }
    return size[x] ;
}
inline void dfs2 ( int x, int tp ) {
    top[x] = tp ;
    dfn[x] = ++clk ;
    register int i, u ;    
    if ( son[x] ) dfs2(son[x], tp) ;
    for ( i = be[x] ; i ; i = nxt[i] ) {
        u = to[i] ;
        if ( u == fa[x] || u == son[x] ) continue ;
        dfs2(u, u) ;
    }
}
int tree[maxn<<2], tag[maxn<<2] ;
inline void push_down ( int h ) {
    if ( tag[h] != zhf ) {
        tree[h<<1] = min(tree[h<<1], tag[h]) ;
        tree[h<<1|1] = min(tree[h<<1|1], tag[h]) ;
        tag[h<<1] = min(tag[h<<1], tag[h]) ;
        tag[h<<1|1] = min(tag[h<<1|1], tag[h]) ;    
        tag[h] = zhf ;
    }
}
inline void push_up ( int h ) { tree[h] = min(tree[h<<1], tree[h<<1|1]) ; }
inline void update ( int h, int l, int r, int x, int y, int v ) {
    if ( x <= l && r <= y ) {
        tree[h] = min(tree[h], v) ;
        tag[h] = min(tag[h], v) ;
        return ;
    }
    push_down(h) ;
    register int mid = (l+r)>>1 ;
    if ( y <= mid ) update ( h<<1, l, mid, x, y, v ) ;
    else if ( x > mid ) update ( h<<1|1, mid+1, r, x, y, v ) ;
    else {
        update ( h<<1, l, mid, x, mid, v ) ;
        update ( h<<1|1, mid+1, r, mid+1, y, v ) ;
    }
    push_up(h) ;
}
inline int query ( int h, int l, int r, int x ) {
    if ( l == r ) return tree[h] ;
    push_down(h) ;
    register int mid = (l+r)>>1 ;
    if ( x <= mid ) return query ( h<<1, l, mid, x ) ;
    else return query ( h<<1|1, mid+1, r, x ) ;
}
inline void Update ( int u, int v, int k ) {
    while ( top[u] != top[v] ) {
        if ( dep[top[u]] > dep[top[v]] ) swap(u, v) ;
        update ( 1, 1, n, dfn[top[v]], dfn[v], k ) ;
        v = fa[top[v]] ;
    }
    if ( dep[u] > dep[v] ) swap(u, v) ;
    if ( u != v ) update ( 1, 1, n, dfn[son[u]], dfn[v], k ) ;
}
int main() {
#ifndef ONLINE_JUDGE
    freopen ( "LG2934.in", "r", stdin ) ;
    freopen ( "LG2934.out", "w", stdout ) ;
#endif
    int i, x, y, z ;
    Read(n) ; Read(m) ;
    for ( i = 1 ; i <= m ; i ++ ) {
        Read(x) ; Read(y) ; Read(z) ;    
        add ( x, y, z ) ;
        add ( y, x, z ) ;
    }
    Dijkstra(1) ;
    for ( i = 2 ; i <= n ; i ++ ) {
        mark[from[i]] = mark[from[i]^1] = 1 ;
        ADD ( i, To[from[i]^1], W[from[i]] ) ;
        ADD ( To[from[i]^1], i, W[from[i]] ) ;
    }
    dep[1] = fa[1] = 1 ;    
    dfs1(1) ;
    dfs2(1, 1) ;
    memset ( tree, zhf, sizeof tree ) ;    
    memset ( tag, zhf, sizeof tag ) ;
    for ( i = 2 ; i <= e ; i += 2 ) {
        if ( mark[i] ) continue ;
        x = To[i] ; y = To[i^1] ;
        Update ( x, y, dis[y] + W[i] + dis[x] ) ;
    }
    
    for ( i = 2 ; i <= n ; i ++ ) {
        x = query ( 1, 1, n, dfn[i] ) ;
        if ( x == zhf ) puts("-1") ;
        else printf ( "%d\n", x - dis[i] ) ;
    }
    return 0 ;
}