建立网站有哪些步骤?,做网站图片为什么不清晰,深圳办公室装饰,安徽网络关键词优化题目背景 狗哥做烂了最短路#xff0c;突然机智的考了Bosh一道#xff0c;没想到把Bosh考住了...你能帮Bosh解决吗#xff1f; 他会给你100000000000000000000000000000000000%10金币w 题目描述 给定n个点的带权有向图#xff0c;求从1到n的路径中边权之积最小的简单路径。… 题目背景 狗哥做烂了最短路突然机智的考了Bosh一道没想到把Bosh考住了...你能帮Bosh解决吗 他会给你100000000000000000000000000000000000%10金币w 题目描述 给定n个点的带权有向图求从1到n的路径中边权之积最小的简单路径。 输入格式 第一行读入两个整数nm表示共n个点m条边。 接下来m行每行三个正整数xyz表示点x到点y有一条边权为z的边。 输出格式 输出仅包括一行记为所求路径的边权之积由于答案可能很大因此狗哥仁慈地让你输出它模9987的余数即可。 废话当然是一个数了w //谢fyszzhouzj指正w 对于20%的数据n10。 对于100%的数据n1000m1000000。边权不超过10000。 输入输出样例 输入 #1复制 3 3
1 2 3
2 3 3
1 3 10 输出 #1复制 9 说明/提示 好好看一看再写哟w 题解 这道题目和通常的最短路的最大差别在于它计算的不是边权之和二是边权乘积。代码如下。里面只有一个小坑就是有两个测试例的数据中边长可能为9987所以如果直接将边的成绩去模9987会产生0从而出现错误结果。程序中对这种情况进行了特判如果出现模后的结果为0则将模后的结果指定为9987。 1 #include iostream2 #include queue3 #include string.h4 5 using namespace std;6 7 struct edge8 {9 int zhongdian, changdu;10 int next 0;11 };12 13 int first[2333];14 15 edge ed[200005];16 17 int n, m, en;18 19 void add_edge( int s, int e, int d )20 {21 en;22 ed[en].next first[s];23 first[s] en;24 ed[en].zhongdian e;25 ed[en].changdu d;26 }27 28 29 const int MAXN 100010;30 const int INF 0x3f3f3f3f;31 int dist[MAXN];32 33 bool use[MAXN];34 35 struct rec36 {37 int p, dist;38 39 rec()40 {41 }42 rec( int a, int b )43 44 {45 p a, dist b;46 }47 };48 49 bool operator (const rec a, const rec b)50 51 {52 return(a.dist b.dist);53 }54 55 priority_queuerec heap;56 57 void dijkstra_heap()58 59 {60 memset( dist, 0x3f3f, sizeof(dist) );61 62 dist[1] 1;63 for ( int a 1; a n; a )64 {65 heap.push( rec( a, dist[a] ) );66 }67 for ( int a 1; a n; a )68 {69 while ( use[heap.top().p] )70 {71 heap.pop();72 }73 rec now heap.top();74 heap.pop();75 int p now.p;76 use[p] true;77 for ( int i first[p]; i; i ed[i].next )78 {79 if ( dist[p] * ed[i].changdu dist[ed[i].zhongdian] )80 81 {82 dist[ed[i].zhongdian] (dist[p] * ed[i].changdu) % 9987;83 if ( dist[ed[i].zhongdian] 0 )84 {85 dist[ed[i].zhongdian] 9987;86 }87 heap.push( rec( ed[i].zhongdian, dist[ed[i].zhongdian] ) );88 }89 }90 }91 }92 93 94 int main()95 {96 cin n m;97 for ( int a 1; a m; a )98 {99 int s, e, d;
100 cin s e d;
101 add_edge( s, e, d );
102 add_edge( e, s, d );
103 }
104 dijkstra_heap();
105 cout dist[n] endl;
106 return(0);
107 } 转载于:https://www.cnblogs.com/zealsoft/p/11530015.html
