最短路

90 阅读 0 评论 60 点赞

我是靠谱客的博主机灵大叔，最近开发中收集的这篇文章主要介绍最短路，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目描述

给你一个n个点，m条边的无向图，定义一条路径的化学系数为路径上所有边的积。
请你找出一条1到n的路径，使它的化学系数最小，并输出这个化学系数对998244353取模
后的结果。

输入格式
第一行两个正整数n,m
接下来m行，每行3个正整数u,v,w，表示从u到v有一条边权为w的边

输出格式
一行一个整数ans表示最小的化学系数

样例输入
3 3
1 2 3
2 3 3
1 3 10

样例输出
9

别看这是边权之积，但是spfa,dijkstra照样能跑。不过因为会爆long long，因此期望得分50.

正解：其实这是一道数学题……

高一的我们都学过，loga + logb = log(a * b)。所以对于每一条边，先取一个log，然后跑一遍最短路，最后还原dis就可。

小优化：为了避免精度问题，可以直接在计算的时候取log，并记录路径，最后反过来求边权之积。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<cstring>
 6 #include<vector>
 7 #include<queue>
 8 using namespace std;
 9 typedef long long ll;
10 const int maxn = 2e3 + 5;
11 const int INF = 0x3f3f3f3f;
12 const int mod = 998244353;
13
14 int n, m;
15 vector<int> v[maxn], c[maxn];
16 bool done[maxn];
17 double dis[maxn];
18 int path[maxn], len[maxn];
19 void spfa(int s)
20 {
21
for(int i = 1; i <= n; ++i) dis[i] = INF;
22
queue<int> q;
23
q.push(s); dis[s] = 0;
24
while(!q.empty())
25 
{
26
int now = q.front(); q.pop(); done[now] = 0;
27
for(int i = 0; i < (int)v[now].size(); ++i)
28 
{
29
if(dis[now] + log(c[now][i]) < dis[v[now][i]])
30 
{
31
dis[v[now][i]] = dis[now] + log(c[now][i]);
32
path[v[now][i]] = now; len[v[now][i]] = c[now][i];
33
if(!done[v[now][i]])
34 
{
35
q.push(v[now][i]); done[v[now][i]] = 1;
36 
}
37 
}
38 
}
39 
}
40
int x = n;
41
ll ans = 1;
42
while(path[x])
43 
{
44
ans *= len[x]; ans %= mod;
45
x = path[x];
46 
}
47
printf("%lldn", ans);
48 }
49
50 int main()
51 {
52
scanf("%d%d", &n, &m);
53
for(int i = 1; i <= m; ++i)
54 
{
55
int a, b, cost; scanf("%d%d%d", &a, &b, &cost);
56 
v[a].push_back(b); c[a].push_back(cost);
57 
v[b].push_back(a); c[b].push_back(cost);
58 
}
59
spfa(1);
60
return 0;
61 }