P6822 [PA2012] Tax

, ,

Description

https://www.luogu.com.cn/problem/P6822

Solution

为什么题解都是建新图啊。虽然很高妙但是想不到啊。

考虑求最短路 dj 的过程，堆里记录每个点的最短路然后取出这个点来扩展。但是这道题只记录点的信息是不够的。我们考虑堆中记录边的信息。记 $d_i$ 表示到第 $i$ 条边 $(x,y,z)$，$x$ 的点权已经算了而 $y$ 的点权还没算的最短路。

考虑更新，枚举 $y$ 的出边 $(y,t,w)$，设其编号为 $j$ 。如果 $z\ge w$ 则 $d_j\gets \min d_i+z$，否则 $d_j\gets d_i+w$。容易想到把边权拍完序以后，重新给边标号，然后用线段树维护。

但是这样太蠢了不是吗？考虑堆的过程，每次拿最小的一条边进行更新。例如 $z\ge w$，如果有更小的 $d_k$ 已经在 $i$ 之前更新过了，则 $i$ 因为在 $k$ 之后出堆而做无效更新。换句话说，每条边只会被 $z\le w$ 的边更新一次，$z\ge w$ 的边更新一次。

这样就可以双指针了。一个小根堆维护 $d_i$，另外一个小根堆维护 $d_i+z$ 。然后双指针更新。事实上我们可以放在一个堆里。

复杂度 $O(m\log m)$。

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
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 400005
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int n,m;
struct yyy {
	int to,w,id;
	bool operator <(const yyy &tmp) const {
		return w<tmp.w;
	}
};
struct node {
	int x,y,z;
}e[maxn];
vector<yyy>to[maxn];
int dis[maxn];
int L[maxn],R[maxn],vis[maxn][2];
priority_queue<pair<int,pair<int,int> > >q;
signed main(void){
	int i,x,y,z,l,r,fl;
	read(n);read(m);
	for (i=1;i<=m;i++) {
		read(x);read(y);read(z);
		to[x].push_back((yyy){y,z,i});
		to[y].push_back((yyy){x,z,i+m});
		e[i].x=x,e[i].y=y,e[i].z=z;
		e[i+m].x=y,e[i+m].y=x,e[i+m].z=z;
	}
	for (i=1;i<=n;i++) sort(to[i].begin(),to[i].end()),R[i]=to[i].size()-1;
	memset(dis,0x3f,sizeof(dis));
	for (auto tmp:to[1]) {
		dis[tmp.id]=tmp.w;
		q.push(mk(-dis[tmp.id],mk(tmp.id,1)));
		q.push(mk(-dis[tmp.id]-tmp.w,mk(tmp.id,0)));
	}
	while (!q.empty()) {
		i=q.top().se.fi;fl=q.top().se.se;q.pop();
		if (vis[i][fl]) continue;vis[i][fl]=1;
		x=e[i].y;
		// gdb(i,dis[i],e[i].x,e[i].y,e[i].z);
		if (fl==0) {
			l=L[x];
			while (l<to[x].size()&&to[x][l].w<=e[i].z) {
				if (dis[to[x][l].id]>dis[i]+e[i].z) {
					dis[to[x][l].id]=dis[i]+e[i].z;
					q.push(mk(-dis[to[x][l].id],mk(to[x][l].id,1)));
					q.push(mk(-dis[to[x][l].id]-e[to[x][l].id].z,mk(to[x][l].id,0)));
				}
				l++;
			} 
			L[x]=l;
		}
		if (fl==1) {
			r=R[x];
			while (r>=0&&to[x][r].w>=e[i].z) {
				if (dis[to[x][r].id]>dis[i]+e[to[x][r].id].z) {
					dis[to[x][r].id]=dis[i]+e[to[x][r].id].z;
					q.push(mk(-dis[to[x][r].id],mk(to[x][r].id,1)));
					q.push(mk(-dis[to[x][r].id]-e[to[x][r].id].z,mk(to[x][r].id,0)));
				} 
				r--;
			}
			R[x]=r;
		}
	}
	int ans=1e18;
	for (i=1;i<=m*2;i++) if (e[i].y==n) ans=min(ans,dis[i]+e[i].z);
	printf("%lld\n",ans);
	return 0;
}
//i=begin && g++ $i.cpp -o $i -std=c++14 && ./$i