第一次用堆优化的模板居然A了，下面给出题面
如果用邻接矩阵的话，原数据空间复杂度为10^8，好像会MLE?所以我选择改用堆优化的dijkstra
这里是需要注意的几点：
1.求最短路时的路径长应该是两条路径长度相乘除以一百（我的方法是直接将路径长转化为小数，最终输出时将答案乘100）；
2.因为要求的是最大可能性，所以建立堆时应当用大根堆；
3.从i到i的几率应该为1，记录最短路的数组初始化的时候应该全部设为0。
剩下的就是标准的dijkstra模板了，代码如下：
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<utility> using namespace std; typedef pair<double,int> pii; struct edge{ int y,ne; double v; }edge[60010]; int n,m,head[10010],len=0; bool vis[10010]; double d[10010]; void addedge(int x,int y,int v) { edge[++len].y=y; edge[len].v=double(v)/100; edge[len].ne=head[x]; head[x]=len; } void init() { memset(head,-1,sizeof(head)); scanf("%d%d",&n,&m); int x,y,v; for (int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&v); addedge(x,y,v); addedge(y,x,v); } } void dijkstra(int s) { priority_queue<pii> q; for (int i=1;i<=n;i++)//初始化 d[i]=0; d[s]=1; memset(vis,false,sizeof(vis)); q.push(make_pair(d[s],s)); while (!q.empty()) { pii temp=q.top(); q.pop(); int x=temp.second; if (vis[x]) continue; vis[x]=true; for (int i=head[x];i!=-1;i=edge[i].ne) if (d[edge[i].y]<d[x]*edge[i].v) { d[edge[i].y]=d[x]*edge[i].v; q.push(make_pair(d[edge[i].y],edge[i].y)); } } printf("%.6lf ",d[n]*100); } int main() { //freopen("add.in","r",stdin); //freopen("add.out","w",stdout); init(); dijkstra(1);//只需要求出1到其他各点的最短路即可 return 0; }