洛谷2384 最短路

题意

给出一个 $n(\le 1000)$ 点 $m(\le 10^6)$ 边的有向图，求 $1\rightarrow n$ 的边权积最小的路径。

题解

因为需要松弛所以不能取模，如果直接乘起来又会爆。不过 $\log(a\times b)=\log(a)+\log(b)$ ，可以改为求边权为 $\log(w)$ 的最短路。

在最短路过程中记录 $y$ 的上一个点 $lst[v]$ 以及两点之间的真实边权，最后统计答案即可。

#include<bits/stdc++.h>
#define mp make_pair
#define pii pair<int,int>
#define ha 9987

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const int N=1005,M=1e6+5;
struct Edge {
    int next,to,w;
} edge[M];
bool vis[N];
double dis[N];
int cnt,head[N],n,m,a,b,c,lst[N],lstv[N];

inline void add(int u,int v,int w)
{
    edge[++cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

inline void dijkstra()
{
    for (int i=2;i<=n;i++) dis[i]=1e9;
    priority_queue <pii,vector<pii>,greater<pii> > q;
    q.push(mp(0,1));
    while (!q.empty())
    {
        int x=q.top().second; q.pop();
        if (vis[x]) continue;
        vis[x]=1;
        for (int i=head[x];i;i=edge[i].next)
        {
            int y=edge[i].to; double w=log(edge[i].w);
            if (dis[x]+w<dis[y])
            {
                dis[y]=dis[x]+w;
                lst[y]=x;
                lstv[y]=edge[i].w;
                q.push(mp(dis[y],y));
            }
        }
    }
}

signed main()
{
    n=read(); m=read();
    for (int i=1;i<=m;i++)
    {
        a=read(); b=read(); c=read();
        add(a,b,c);
    }
    dijkstra();
    int ans=1;
    for (int i=n;lstv[i];i=lst[i]) ans=ans*lstv[i]%ha;
    return !printf("%d",ans);
}