priority 不是大根堆吗
by Lightning_Creeper @ 2023-08-10 14:17:03
```cpp
#include<bits/stdc++.h>
#define M 200005
using namespace std;
int n,m,s,A,B;
priority_queue<pair<double ,int> >q;
int qnext[M],ver[M],head[M],num;
bool b[M];
double dis[M],tance[M];
void add(int fr,int to,double di)
{
dis[++num]=di;
ver[num]=to;
qnext[num]=head[fr];
head[fr]=num;
}
void Dij(int u)
{
for(int i=1;i<=m;i++)
tance[i]=0;
tance[u]=1.00;
q.push(make_pair(1.00,u));
while(q.size())
{
int cnt;
cnt=q.top().second;
q.pop();
if(b[cnt]==1)
continue;
b[cnt]=1;
for(int i=head[cnt];i;i=qnext[i])
{
int y=ver[i];
double z=dis[i];
if(tance[y]<tance[cnt]*z*1.00)
tance[y]=tance[cnt]*z*1.00;
q.push(make_pair(tance[y],y));
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
double d;
scanf("%d%d%lf",&x,&y,&d);
add(x,y,1-0.01*d);
add(y,x,1-0.01*d);
}
scanf("%d%d",&A,&B);
Dij(A);
double ff=100/tance[B];
printf("%.8lf",ff);
return 0;
}
```
by A_chicken_boy @ 2023-08-10 14:19:14
把
```cpp
q.push(make_pair(-tance[y],y));
```
改成
```cpp
q.push(make_pair(tance[y],y));
```
by A_chicken_boy @ 2023-08-10 14:20:08
@[Koshka_Dlq33](/user/774204) @[Lightning_Creeper](/user/386547)
已过，谢谢大佬
by F_Q_chicken @ 2023-08-10 14:21:08