本文主要是介绍洛谷 P2384 最短路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
P2384 最短路
题目提供者Bosh
标签 图论 最短路 难度 普及/提高-
狗哥做烂了最短路，突然机智的考了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 3 1 2 3 2 3 3 1 3 10
输出样例#1： 9
说明
/*
直接spfa暴力.
数据很水.
如果边权值大一点就不能这样搞了.
*/
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#define mod 9987
#define MAXM 1000001
#define MAXN 1001
using namespace std;
int n,m,g[MAXN][MAXN],head[MAXN],cut,pre[MAXN],ans=1;
bool b[MAXN];
long long dis[MAXN];
struct data{int v,next,z;double x;}e[MAXM];
int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();return x*f;
}
void add(int u,int v,int z)
{e[++cut].v=v;e[cut].x=log(z);e[cut].z=z;e[cut].next=head[u];head[u]=cut;
}
void spfa()
{memset(dis,127,sizeof dis);queue<int>q;q.push(1);dis[1]=1;while(!q.empty()){int u=q.front();q.pop();for(int i=head[u];i;i=e[i].next){int v=e[i].v;if(dis[v]>dis[u]*e[i].z){dis[v]=dis[u]*e[i].z;pre[v]=u;if(!b[v]) b[v]=true,q.push(v);}}}
}
int main()
{int x,y,z;n=read(),m=read();for(int i=1;i<=m;i++){x=read(),y=read(),z=read();g[x][y]=z;add(x,y,z);}spfa();printf("%d",dis[n]%mod);return 0;
}/*
单源询问两点之间最小积路.
比较好的一种做法.
然后用log性质.
log(n*m)=log(n)+log(m)
然后我想最后取2的dis[n]次方作为ans.
但是因为double的缘故这个ans是错误的.
so我们在保证正确性的情况下记录路径求ans.
*/
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#define mod 9987
#define MAXM 1000001
#define MAXN 1001
using namespace std;
int n,m,g[MAXN][MAXN],head[MAXN],cut,pre[MAXN],ans=1;
bool b[MAXN];
double dis[MAXN];
struct data{int v,next,z;double x;}e[MAXM];
int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();return x*f;
}
void add(int u,int v,int z)
{e[++cut].v=v;e[cut].x=log(z);e[cut].z=z;e[cut].next=head[u];head[u]=cut;
}
void spfa()
{memset(dis,127,sizeof dis);queue<int>q;q.push(1);dis[1]=0;while(!q.empty()){int u=q.front();q.pop();for(int i=head[u];i;i=e[i].next){int v=e[i].v;if(dis[v]>dis[u]+e[i].x){dis[v]=dis[u]+e[i].x;pre[v]=u;if(!b[v]) b[v]=true,q.push(v);}}}
}
int main()
{int x,y,z;n=read(),m=read();for(int i=1;i<=m;i++){x=read(),y=read(),z=read();g[x][y]=z;add(x,y,z);}spfa();x=n;while(pre[x]){ans=(ans*g[pre[x]][x]%mod)%mod;x=pre[x];}printf("%d",ans);return 0;
}这篇关于洛谷 P2384 最短路的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
