Hangdian Multi-School-Slipper- (tree map conversion + virtual point mapping)

Slipper

题意：
就是给你一个以1为根的树,Then each side has its own cost.然后小AYou can use any time magic,Use a magic can make depth is poor forkThe two points can transfer each other,花费为m.然后给你起点和终点,Ask your minimum cost.

思考：
1.See this tree problem,My feeling is that the treedp.But wanted to think how todp呢？The jump is not update transfer ah.So here is a treedp就不可以了.Feeling is supposed to be a problem,But later had a lot of,So, it is not problem.
2.Since then feel the treedp不能做,Also pleaseA到B的最短距离,It can build figure and then run the most short circuit.Here are simple,Built figure is established between can jump what point to build map good.You can put the depth of each point out maintenance,那么深度为aTo a depth ofa+kTo build edge,If violence enumerated little built side it isnn的复杂度.Actually can create a virtual point,然后aThe point set of the virtual point,The right of the point set even imaginary point.这样复杂度是4n的.Must be a directed edge to edge to establish.
3.After establishing the whole figure out,跑一边distra就可以了.If the card space time,可以把vectorWith adjacency list.初始化vectorAlso to the least amount of initialization,To the best of this time space optimization.At that time when I ordered to build virtual edge make wrong,傻逼了,Ran slowly.Later must draw a chart,Can't directly go up to,容易出错.
4.当然,This way of building figure can also be like next question,不用维护vectorSave the depth of the point.Directly to their own virtual point and other points to go,这样更快.While less,Points less.

代码：

#include<bits/stdc++.h>
#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(); //The least amount of initialization
		for(int i=1;i<=cnt;i++) e[i].clear(); //The least amount of initialization,用多少,初始化多少
		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的没有,就提前退出,The following is not built side,浪费.
			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;
}

Acwing-NyaFigure the most short circuit

题意：
就是给你n个点,Each point has his layer.然后给你m条边,每条边有个花费.Then point between the adjacent layers can also move to each other,But cost isk.问你从1号点走到n号点的最小花费.

思考：
1.It is clear that this problem is the same,There is point to the adjacent layer built side each other,If violence built side must also timeout.So is established between two layers of virtual point is ok.But submit found or timeout？Stock with adjacency list also not line, on the edge of.
2.Then I doubt deposit layer countvector可能会超时,And built by the side too much？.If I change mode of built figure？对于每个点,His imaginary point is his layer+n.This will only at mostn个虚点,And before one is2n个虚点.对于每个点,Let his own imaginary point even to their own time0,Even around on two points when others spendk.
3.So always establish the edge3n个,Add itself to2m个.也就是51e5个边,2*1e5个点.一定要算好内存,This kind of time and memory card,As far as possible good open minimum.

代码：

#include<bits/stdc++.h>
#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是点的个数,The rest is the number of edge
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++) //Let his own points to is0,I go to someone else's imaginary point isk 
		{
    
			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 the imaginary point exist
			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;
}

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