首页 > 代码库 > 边权之积最小的路径

边权之积最小的路径

2024-09-20 07:01:33   215人阅读

题目背景

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

他会给你100000000000000000000000000000000000%10金币w

题目描述

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

输入输出格式

输入格式：

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

输出格式：

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

废话当然是一个数了w

//谢fyszzhouzj指正w

对于20%的数据，n<=10。

对于100%的数据，n<=1000，m<=1000000。边权不超过10000。

输入输出样例

输入样例#1：
3 31 2 3 2 3 3 1 3 10
输出样例#1：
9

说明

好好看一看再写哟w

思路

logM+logN=long(N*M)

然后就可以转化成常规的SPFA+记录路径了。

代码实现

 1 #include<cmath> 2 #include<cstdio> 3 #include<cstring> 4 const int maxn=1e3; 5 const int maxm=1e6; 6 const int mod=9987; 7 int n,m,ans=1; 8 int a,b,c; 9 int h[maxn],hs;10 struct edge{int q,s,n,t;double w;}e[maxm];11 void add(int x,int y,double z){e[++hs]=(edge){x,y,h[x],z,log(z)},h[x]=hs;}12 int q[maxm],gj[maxn],head,tail;13 double d[maxn];14 void SPFA(int s,int t){15     for(int i=1;i<=n;i++) d[i]=1e5;16     head=tail=0;17     q[head++]=s,d[s]=0;18     while(head>tail){19         a=q[tail++];20         for(int i=h[a];i;i=e[i].n)21         if(d[a]+e[i].w<d[e[i].s]){22             gj[e[i].s]=i;23             d[e[i].s]=d[a]+e[i].w;24             q[head++]=e[i].s;25         }26     }27 }28 int main(){29     scanf("%d%d",&n,&m);30     for(int i=1;i<=m;i++){31         scanf("%d%d%d",&a,&b,&c);32         add(a,b,c);33     }34     SPFA(1,n);35     for(int i=gj[n];i;i=gj[e[i].q]) ans=(ans*e[i].t)%mod;36     printf("%d\n",ans);37     return 0;38 }

发题解的同学好强。

边权之积最小的路径


联系
我们