没看见SPFA算法,写了个SPFA的题解
SPFA更加通用,可以用来解决>0的乘法最大最小值问题
#include<bits/stdc++.h>
using namespace std;
const int N =2010,M=1e5*2+10;
int n,m,S,T;
int h[N],e[M],ne[M],idx;
double w[M];
double dist[N];
bool st[N];
void add(int a,int b,double c)
{
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void spfa()
{
queue<int> q;
q.push(S);
dist[S]=1;
while(q.size())
{
auto t = q.front();
q.pop();
st[t]=0;
for(int i = h[t];~i;i=ne[i])
{
int j = e[i];
if(dist[j]<dist[t]*w[i])
{
dist[j]=dist[t]*w[i];
if(!st[j])
{
q.push(j);
st[j]=1;
}
}
}
}
}
int main()
{
cin>>n>>m;
memset(h,-1,sizeof h);
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
double z = (100.0-c)/100;
add(a,b,z),add(b,a,z);
}
cin>>S>>T;
spfa();
printf("%.8lf\n",100/dist[T]);
return 0;
}