UVA10917 【Walk Through the Forest】 题解

算是比较板子的题了。不懂为什么难度被评到了紫题……

$\texttt{Description}$

给你一个 $n$ 个点，$m$ 条边的图，令 $dis_i$ 表示编号为 $2$ 的点到点 $i$ 的最短路，求从点 $1$ 出发，经过原图中 $dis_{from}>dis_{to}$ 的边到达点 $2$ 的方案数，$from,to$ 分别表示这条边的起点和终点。

$\texttt{Data Range}:n\le 1000,m\le n^2$。

$\texttt{Solution}$

跑一边最短路那是必须的，建议不要用某死了的算法。

那么建一个新的图，对于原图一条 $u\rightarrow v$ 的点，当且仅当 $dis_u>dis_v$ 在新图中加入这条边。

新的图一定是一个 DAG，dp 求解 $1\rightarrow 2$ 的方案数即可，我建了个隐式反图。

时间复杂度 $O(mlogn)$。

按理说这题数据范围珂以给到 $1\le n,m,\le 500000$ 啊/yiw

$\texttt{Code}$

#include <cstdio>
#include <queue>
#include <cstring>

typedef std::pair<int, int> PII;
std::priority_queue<PII, std::vector<PII>, std::greater<PII> > q;
struct Edge {
	int to, nxt, w;
} e[2000005];
int dis[1005], head[1005], dp[1005], tot, n, m;
bool mp[1005][1005], done[1005];
inline void AddEdge(const int u, const int v, const int w) {
	e[++ tot].to = v, e[tot].nxt = head[u], e[tot].w = w, head[u] = tot;
}
void Dijkstra() {
	memset(dp, 0, sizeof dp);
	memset(dis, 0x3f, sizeof dis);
	memset(done, 0, sizeof done);
	dp[2] = 1;
	q.push(std::make_pair(dis[2] = 0, 2));
	while (q.size()) {
		int u(q.top().second);
		q.pop();
		if (done[u]) continue;
		done[u] = true;
		for (int i(head[u]); i; i = e[i].nxt) {
			int v(e[i].to);
			if (dis[u] + e[i].w < dis[v])
				q.push(std::make_pair(dis[v] = dis[u] + e[i].w, v));
		}
	}
}
int DP(const int u) {
	if (dp[u]) return dp[u];
	for (int i(1); i <= n; ++ i)
		if (dis[i] < dis[u] && mp[i][u]) dp[u] += DP(i);
	return dp[u];
}

signed main() {
	while (true) {
		scanf("%d", &n);
		if (!n) return 0;
		memset(head, 0, sizeof head);
		memset(mp, 0, sizeof mp);
		tot = 0;
		scanf("%d", &m);
		for (int i(1); i <= m; ++ i) {
			int u, v, w;
			scanf("%d%d%d", &u, &v, &w);
			mp[u][v] = mp[v][u] = true;
			AddEdge(u, v, w), AddEdge(v, u, w);
		}
		Dijkstra();
		printf("%d\n", DP(1));
	}
}