本文主要是介绍洛谷P2384最短路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目背景
狗哥做烂了最短路，突然机智的考了Bosh一道，没想到把Bosh考住了…你能帮Bosh解决吗？
他会给你100000000000000000000000000000000000 %10 金币（滑稽）
题目描述
给定n个点的带权有向图，求从1到n的路径中边权之积最小的简单路径。
输入输出格式
输入格式：
第一行读入两个整数n，m，表示共n个点m条边。 接下来m行，每行三个正整数x，y，z，表示点x到点y有一条边权为z的边。
输出格式：
输出仅包括一行，记为所求路径的边权之积，由于答案可能很大，因此狗哥仁慈地让你输出它模9987的余数即可。
对于20%的数据，n<=10。
对于100%的数据，n<=1000，m<=1000000。边权不超过10000。
输入输出样例
输入样例#1:
3 3
1 2 3
2 3 3
1 3 10
输出样例#1:
9
（这题数据好水，本来以为要爆ll，可是直接过了）
思路：n<=1000，一看到数据就觉得要用Dijkstra，而且邻接矩阵也足够存边了。
注意：1.初始化：边无穷大（0x7fffffff），最短路径fi是从1到i的边的权值，判白点的数组bi=0。
2.更新的时候，要判边是否连通，不然乘了之后有可能会爆回负数，结果就错了。
3.过程中不用mod，也不能mod（想一想，为什么），最后再mod。
P.S.本来觉得过不了，没想到过了^_^
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m;
int edge[1001][1001];//邻接矩阵
ll f[1001];//单源最短路
int b[1001];//标记白点
int main(){cin>>n>>m;//初始化for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){edge[i][j]=0x7fffffff;}f[i]=0xfffffff;b[i]=0;}//输入for(int i=1;i<=n;i++){int x,y,v;cin>>x>>y>>v;edge[x][y]=v;}//初始化for(int i=1;i<=n;i++){f[i]=edge[1][i];}f[1]=0;//起点到起点的最短路是0b[1]=1;//标记成白点for(int i=1;i<=n;i++){int mn=0x7fffffff;int k=0;for(int j=1;j<=n;j++){if((!b[j])&&(f[j]<mn)){//如果不是白点，而且是目前最短的mn=f[j];k=j;}}if(k==0)break;//无法更新，退出b[k]=1;//标记白点//更新所有点for(int j=1;j<=n;j++){if((edge[k][j]!=0x7fffffff)&&(f[j]>f[k]*edge[k][j])){f[j]=f[k]*edge[k][j];}}}cout<<f[n]%9987;//记得取模return 0;
}这篇关于洛谷P2384最短路的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
