14177: 【原4177】最小乘积路径

题目

题目描述

author: LH 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4177 

Description

听说小蔡同学给大家讲述了树和图相关的知识。苏爷觉得实在是太水了，于是安排小H同学出题。
比如说，题面可以这样，通往成功的路径有很多，你在1处，成功在N处。
你每走一条路就会掉z的头发，但是这样如何脱发最少就变成了最短路，那也太简单了！
以及发量的脱落显然是难以估量的级别，于是你所走的路径上所有值的乘积就是你脱落的发量。
由于脱发量即有可能超越2147483649，小H统计起来不方便。
于是希望最后脱发量最小，并将结果Mod 998244353输出。

简而言之，就是需要你求一条最小乘积路径。

Input Format

第一行为两个正整数N，M。N表示点数，M表示边数。
接下来又M行，每行三个正整数x,y,z。表示从x点到y点有一条长度为z的无向边。
起点为1，终点为N，保证边权均小于等于1000

Output Format

仅有一行，输出最小乘积对998244353取模后的答案

Sample1 Input

4 4
1 2 3
1 3 2
2 4 4
3 4 7

Sample1 Output

12

HINT:

最小乘积取模之后一定是最小么(⊙o⊙)？
本着严格保护头发的原则，多一根都不给分哦。

数据规模

对于20%的数据，\(1 \leq N \leq 5\)
对于40%的数据，\(1 \leq N \leq 200\)
对于70%的数据，保证最小乘积不会超过int
对于100%的数据，\(1 \leq N \leq 50000,1 \leq M \leq 200000\)

zqy2018's solution

/*
    See the solution at https://github.com/zqy1018/sjtu_oj_solutions/blob/master/solutions/sjtu4177.md
*/
#include <bits/stdc++.h>
#define INF 2000000000
#define M 998244353
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, m, to[400005], nxt[400005], at[50005] = {0}, cnt = 0;
int ww[400005], dis[50005];
double w[400005], dd[50005];
priority_queue<pair<double, int> > pq;
void init(){
    n = read(), m = read();
    for (int i = 1; i <= m; ++i){
        int u = read(), v = read(), www = read();
        to[++cnt] = v, nxt[cnt] = at[u], at[u] = cnt;
        to[++cnt] = u, nxt[cnt] = at[v], at[v] = cnt;
        w[cnt] = w[cnt - 1] = log(www);
        ww[cnt] = ww[cnt - 1] = www;
    }
    for (int i = 1; i <= n; ++i)
        dd[i] = INF;
    dd[1] = 0, dis[1] = 1;
}
void solve(){
    pq.push(make_pair(0, 1));
    for (int i = 1; i <= n; ++i){
        while (!pq.empty()){
            if (-pq.top().first > dd[pq.top().second] + 1e-4)
                pq.pop();
            else break;
        }
        if (pq.empty()) break;
        int minp = pq.top().second;
        pq.pop();
        for (int j = at[minp]; j; j = nxt[j]){
            if (dd[to[j]] > dd[minp] + w[j])
                dd[to[j]] = dd[minp] + w[j], 
                dis[to[j]] = 1ll * dis[minp] * ww[j] % M, 
                pq.push(make_pair(-dd[to[j]], to[j]));
        }
    }
    printf("%d\n", dis[n]);
}
int main(){
    init();
    solve();
    return 0;
}