P2384 最短路

题目

（直接从洛谷网站上复制的div）

题目背景

狗哥做烂了最短路，突然机智的考了 Bosh 一道，没想到把 Bosh 考住了...你能帮 Bosh 解决吗？

题目描述

给定 $n$ 个点的带权有向图，求从 $1$ 到 $n$ 的路径中边权之积最小的简单路径。

输入格式

第一行读入两个整数 $n$，$m$，表示共 $n$ 个点 $m$ 条边。 接下来 $m$ 行，每行三个正整数 $x$，$y$，$z$，表示点 $x$ 到点 $y$ 有一条边权为z的边。

输出格式

输出仅包括一行，记为所求路径的边权之积，由于答案可能很大，因此狗哥仁慈地让你输出它模 $9987$ 的余数即可。

废话当然是一个数了w

//谢fyszzhouzj指正w

输入输出样例

输入 #1 复制

3 3
1 2 3 
2 3 3 
1 3 10

输出 #1 复制

9

说明/提示

对于 $20\%$ 的数据，$n\leq 10$。

对于 $100\%$ 的数据，$n\leq 10^3$，$m\leq 10^6$。边权不超过 $10^4$。

题解

这道题注意点：乘积。一般有两种解决方式：

• 对数
• 记录路径

对数的话涉及到$\log$然后再还原到int可能会出现问题（反正我是失败了，我，菜），所以这里介绍第二种方法：直接记录路径，下面是具体分析。

记录路径

我们可以发现，在dijkstra的void里更新判断的if里面更新时，更新的情况一定是优于原来的的。那么就在更新时记录前继呗。然后由于我们是邻接表存图，所以再记录一下边权就完事了。

代码

#include <cstdio>
#include <queue>
#include <iostream> 
#include <cmath>
#define int long long

using namespace std;

const int maxn = 1000005;

int head[maxn];
int ecnt = 2, n, m;
double dis[maxn];
int pre[maxn];
int pre_weight[maxn];
bool vis[maxn];

struct edge {
	int to, next, w;
} g[maxn << 1];
void add_edge(int u, int v, int w) {
	g[ecnt] = (edge) { v, head[u], w };
	head[u] = ecnt ++;
}

struct node {
	double dis, pos;
	friend bool operator < (const node &a, const node &b) {
		return a.dis > b.dis;
	}
};
priority_queue<node> q;

void dijkstra() {
	for (int i = 1; i <= n; i ++) dis[i] = 8e18;
	dis[1] = 0; q.push((node) { 0, 1 });
	while (!q.empty()) {
		int u = q.top().pos; q.pop();
		if (vis[u]) continue;
		vis[u] = true;
		for (int e = head[u]; e != 0; e = g[e].next) {
			int v = g[e].to;
			if (dis[v] > dis[u] + log2(g[e].w)) {
				dis[v] = dis[u] + log2(g[e].w);
				q.push((node) { dis[v], v });
				pre[v] = u;
				pre_weight[v] = g[e].w;
			}
		}
	}
}

signed main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i ++) {
		int x, y, z; cin >> x >> y >> z;
		add_edge(x, y, z);
		if (z == 0) {
			cout << 0 << endl;
			return 0;
		} 
	}
	dijkstra();
	int i = n;
	int ans = 1;
	while (pre[i] != 0) {
		ans = ans * pre_weight[i];
		ans = ans % 9987;
		i = pre[i];
	}
	cout << ans << endl; 
}