【洛谷 2384】最短路

题目背景

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

他会给你100000000000000000000000000000000000金币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

说明

好好看一看再写哟w

题解：简单的dijkstra对就这样，加法改成乘法。

（看错题目，有向图以为无向，哎找了好久）

#include<cstdio> #include<iostream> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> typedef long long ll; using namespace std; const int oo=2147483647; const int mod=9987; int n,m,dis[5005],vis[5005],a[5005][5005]; int main(){ freopen("2384.in","r",stdin); freopen("2384.out","w",stdout); scanf("%d %d",&n,&m); int x,y,z; //memset(a,100000,sizeof(a)); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i][j]=100000; for(int i=1;i<=m;i++){ cin>>x>>y>>z; a[x][y]=z; //a[y][x]=z; } for(int i=1;i<=n;i++) dis[i]=a[1][i]; dis[1]=0; vis[1]=1; for(int i=1;i<=n;i++){ int now=oo,ii; for(int j=1;j<=n;j++) if(vis[j]==0 && dis[j]<now){ ii=j; now=dis[j]; } vis[ii]=1; for(int j=1;j<=n;j++) if(dis[ii]*a[ii][j]<dis[j]) dis[j]=dis[ii]*a[ii][j]; } cout<<dis[n]%mod<<endl; return 0; }

 

转载于:https://www.cnblogs.com/wuhu-JJJ/p/11141326.html

相关资源：各显卡算力对照表！