杭电多校-Slipper-(树图转化+虚点建图)

Slipper

题意：
就是给你一个以1为根的树，然后每条边有各自的花费。然后小A可以使用任意次魔法，使用一次魔法可以使得深度差为k的两个点可以互相传送，花费为m。然后给你起点和终点，问你最小花费。

思考：
1.看到这种树上问题，我就感觉是树上dp。但是想了想怎么dp呢？这个跳跃是不能更新转移的呀。所以这里树形dp就不可以了。感觉应该是个难题，但是后来过的很多，那么就不是难题了。
2.那么既然感觉树上dp不能做，还求A到B的最短距离，这不就可以建图然后跑最短路。到这里其实就简单了，建图就是建立可以跳跃的哪些点之间要建好图。那么可以先把每个深度的点维护出来，那么深度为a的到深度为a+k的进行建边，如果暴力枚举点点建边这是nn的复杂度。其实可以建立一个虚点，然后a的点集连虚点，右边的点集连虚点。这样复杂度是4n的。一定是有向边有向边的建立。
3.整个图建立出来后，跑一边distra就可以了。如果卡空间卡时间，可以把vector换成邻接表。初始化vector也要最少的初始化，这样时间空间就优化到极致了。当时我虚点建边的时候建立错了，傻逼了，就跑的很慢。以后一定要画一下图，不能直接上去搞，容易出错。
4.当然，这题的建图方式也可以和下一题一样，不用维护vector存这个深度的点。直接让自己连自己的虚点和别人的虚点就行了，这样更快。边更少，虚点更少。

代码：

#include
#define ll long long
#define PII pair<ll,int >
#define fi first
#define se second
#define pb push_back
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

using namespace std;

const ll N = 1e6+50,inf = 1e18;

int T,n,m,k;
int dep[N];
int st,ed;
ll dist[3*N];
bool vis[3*N]; //卡空间，记得关longlong，开bool
int cnt,maxn;

vector<int > v[N];
vector<PII > e[3*N];

void dfs(int now,int p)
{
	dep[now] = dep[p]+1;
	v[dep[now]].pb(now);
	maxn = max(maxn,dep[now]);
	for(auto t:e[now])
	{
		int spot = t.fi;
		if(spot==p) continue;
		dfs(spot,now);
	}
}

void distra()
{
	for(int i=1;i<=cnt;i++) dist[i] = inf,vis[i] = 0;
	priority_queue<PII,vector<PII>,greater<PII> > q;
	q.push({0,st});
	dist[st] = 0;
	while(q.size())
	{
		auto t = q.top();q.pop();
		int now = t.se,dis = t.fi;
		if(vis[now]) continue;
		vis[now] = 1;
		for(auto tt:e[now])
		{
			int spot = tt.fi,w = tt.se;
			if(dist[spot]>dist[now]+w)
			{
				dist[spot] = dist[now]+w;
				q.push({dist[spot],spot});
			}
		}
	}
}

signed main()
{	
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++) v[i].clear(); //最少的初始化
		for(int i=1;i<=cnt;i++) e[i].clear(); //最少的初始化,用多少，初始化多少
		for(int i=1;i<n;i++)
		{
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			e[a].pb({b,c});
			e[b].pb({a,c});
		}
		scanf("%d%d%d%d",&k,&m,&st,&ed);
		dfs(1,0);
		cnt = n; //cnt最大3*n
		for(int i=1;i<=n;i++)
		{
			int r = i+k;
			if(r>maxn) break; //如果深度为r的没有，就提前退出，下面的就不建边了，浪费。
			cnt++;
			for(auto t:v[i]) e[t].pb({cnt,m});
			for(auto t:v[r]) e[cnt].pb({t,0});
			cnt++;
			for(auto t:v[r]) e[t].pb({cnt,m});
			for(auto t:v[i]) e[cnt].pb({t,0});
		}
		distra();
		printf("%lld\n",dist[ed]);
	}
	return 0;
}
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

Acwing-Nya图最短路

题意：
就是给你n个点，每个点有自己所在的层数。然后给你m条边，每条边有个花费。然后相邻层之间的点也可以互相移动，不过花费是k。问你从1号点走到n号点的最小花费。

思考：
1.很明显这个题也是一样，对于相邻的层的点要相互建边，如果暴力建边肯定也超时。所以也是两层之间建立虚点就可以了。但是提交发现还是超时？把存边的换成邻接表也不行。
2.然后我就怀疑存层数点的vector可能会超时，还有建的边太多？。如果我换种建图方式呢？对于每个点，他的虚点就是他的层数+n。这样最多只会n个虚点，而前一个是2n个虚点。对于每个点，让他自己的虚点连向自己的时候花费0，自己连上左右两个别人虚点的时候花费k。
3.这样总建立的边就3n个，加上本身给的2m个。也就是51e5个边，2*1e5个点。一定要算好内存，这种卡时间和内存的，尽量算好开最小。

代码：

#include
#define fi first
#define se second
#define pb push_back
#define db double
#define ll long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
		
using namespace std;
const ll mod = 1e9+7,inf = 1e18;
const int N = 200010,M = 500100;

int T,n,m,k;
int va[N];
ll dist[N];
bool vis[N];

int h[N],e[M],ne[M],w[M],idx;
//h是点的个数，剩下的都是边的个数
void add(int a,int b,int c)
{
	w[idx] = c;
	e[idx] = b;
	ne[idx] = h[a];
	h[a] = idx++;
}

void init()
{
	idx = 0;
	for(int i=0;i<=2*n;i++) h[i] = -1;
}

void distra()
{
	for(int i=1;i<=2*n;i++) dist[i] = inf,vis[i] = 0;
	priority_queue<PII,vector<PII>,greater<PII> > q;
	q.push({0,1});
	dist[1] = 0;
	while(q.size())
	{
		auto t = q.top();q.pop();
		int now = t.se,dis = t.fi;
		if(now==n) return ;
		if(vis[now]) continue;
		vis[now] = 1;
		for(int i=h[now];i!=-1;i=ne[i])
		{
			int spot = e[i],x = w[i];
			if(dist[spot]>dist[now]+x)
			{
				dist[spot] = dist[now]+x;
				q.push({dist[spot],spot});
			}
		}
	}	
}

signed main()
{
	scanf("%d",&T);
	for(int cs=1;cs<=T;cs++)
	{
		scanf("%d%d%d",&n,&m,&k);
		init();
		for(int i=1;i<=n;i++) scanf("%d",&va[i]);
		for(int i=1;i<=n;i++) //让自己的虚点走向自己是0，自己走向别人的虚点是k 
		{
			int now = va[i]+n;
			int l = va[i]-1+n,r = va[i]+1+n;
			add(now,i,0);
			if(l>n) add(i,l,k); //如果这个虚点存在的话
			if(r>n) add(i,r,k);
		}
		while(m--)
		{
			int a,b,c;
			cin>>a>>b>>c;
			add(a,b,c);
			add(b,a,c);
		}
		distra();
		if(dist[n]==inf) dist[n] = -1;
		printf("Case #%d: %lld\n",cs,dist[n]);
	}
	return 0;
}
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

总结：
多多总结。当出错的时候，考虑清楚，到底是哪里错了，多检查。多多积累经验。