HDU - 7187-Slipper (最短路、建图优化)

题意：

给出n个结点，n-1条无向边，经过每条边的代价为w,以结点1为根节点的树，对于相差k层的结点，可以花费代价p抵达，问结点s到t的最短路径。

分析：

考虑对于每层的每个点建立到相差k层的点的边，极端情况为 $O(n^2)$ 的复杂度，需要优化。

考虑对于每层额外添加点。层与层之间的边通过虚点连接，代价为p。

若只添加一个点，则该点到这一层的点必须是双向的，但这样会使同层之间可以直接抵达。错解。

考虑添加两个点，一个点(a)建立该层的点到a的单向边，代价为0，另一个点(b)建立b到该层的点的单向边，代价为0。层与层之间的边连接如下图所示：

解题步骤：

由上分析知，先正常建图，然后dfs出图的深度，同时添加每一层的点到虚点的边。跑一遍迪杰斯特拉即可。

邻接表：

const int N = 1e6 + 10;
const ll INF = 0x3f3f3f3f3f3f3f3f;
struct node {
	int v; int w;
};

int n; 
vector<node>g[N * 3];
int dep[N], maxdep = 0;
ll dis[N * 3];
int vis[N * 3];
priority_queue<pair<ll, int>>q;

void init(int n) {
	for (int i = 0; i <= n; i++) {
		g[i].clear(), g[i + n].clear(), g[i + n * 2].clear();
		dis[i] = INF, dis[i + n] = INF, dis[i + n * 2] = INF;
		vis[i] = 0, vis[i + n] = 0, vis[i + n * 2] = 0;
		dep[i] = 0;
	}
	maxdep = 0;
}

void add(int u, int v, int w) {
	g[u].push_back({ v,w });
}

void dfs(int u, int f) {
	dep[u] = dep[f] + 1;
	maxdep = max(maxdep, dep[u]);
	for (auto it : g[u]) {
		int v = it.v;
		if (v == f)continue;
		dfs(v, u);
	}
	add(u, dep[u] + n, 0);
	add(dep[u] + n * 2, u, 0);
}

void dij(int s) {
	dis[s] = 0;
	q.push({ 0,s });
	while (q.size()) {
		auto it = q.top(); q.pop();
		int u = it.second; if (vis[u])continue;
		vis[u] = 1;
		for (auto t : g[u]) {
			int v = t.v, w = t.w;
			if (dis[v] > dis[u] + w) {
				dis[v] = dis[u] + w;
				q.push({ -dis[v],v });
			}
		}
	}
}

void solve() {
	cin >> n;
	init(n);
	for (int i = 1; i < n; i++) {
		int u, v, w; cin >> u >> v >> w;
		add(u, v, w);
		add(v, u, w);
	}
	int k, p; cin >> k >> p;
	int s, t; cin >> s >> t;
	dfs(1, 0);
	for(int i = 1; i <= n; i++) {
		if (i + k > maxdep)break;
		add(i + n, i + k + n * 2, p);
		add(i + k + n, i + n * 2, p);
	}
	dij(s);
	cout << dis[t] << endl;
}

链式前向星：

struct node {
	int v, ne;
	ll w;
}e[N * 4];
int h[N * 4], idx;
int dep[N * 2], maxdep;
ll dis[N * 4];
int vis[N * 4];
priority_queue<pair<ll, int>>q;
int n; 

void add(int u, int v, int w) {
	e[idx] = { v,h[u],w };
	h[u] = idx++;
}

void dfs(int u, int f) {
	dep[u] = dep[f] + 1;
	maxdep = max(maxdep, dep[u]);
	for (int i = h[u]; i != -1; i = e[i].ne) {
		int v = e[i].v;
		if (v == f)continue;
		dfs(v, u);
	}
	add(u, dep[u] + n, 0);
	add(dep[u] + n * 2, u, 0);
}

void solve() {
	cin >> n;
	memset(h, -1, sizeof h);
	idx = 0;
	maxdep = 0;
	for (int i = 1; i < n; i++) {
		int u, v, w; cin >> u >> v >> w;
		add(u, v, w);
		add(v, u, w);
	}
	dfs(1, 0);

	int k, p; cin >> k >> p;
	for (int i = 1; i <= maxdep; i++) {
		if (i + k > maxdep)break;
		add(i + n, i + k + n * 2, p);
		add(i + k + n, i + n * 2, p);
	}
	for (int i = 0; i <= n; i++) {
		dis[i] = INF, dis[i + n] = INF, dis[i + n * 2] = INF;
		vis[i] = 0, vis[i + n] = 0, vis[i + n * 2] = 0;
	}
	int s, t; cin >> s >> t;
	dis[s] = 0;
	q.push({ 0,s });
	while (q.size()) {
		auto it = q.top(); q.pop();
		int u = it.second; if (vis[u])continue;
		vis[u] = 1;
		for (int i = h[u]; i != -1; i = e[i].ne) {
			int v = e[i].v; ll w = e[i].w;
			if (dis[v] > dis[u] + w) {
				dis[v] = dis[u] + w;
				q.push({ -dis[v], v });
			}
		}
	}
	cout << dis[t] << endl;
}