正确性证明:
对于最短路,我们要保证边是正的递增,才能保证每次找到的最小的 dist 再也不会被更新掉.那么对于最长路,我们只要保证dist是越来小的,才能保证每次我们找到的最大的距离点再也不会被更新掉。那么边权的加肯定是不满足的,什么是满足的?本题的边权的乘积,而且是0∼1的边权,才能保证dist越来越小。
求最长路,即边权乘积最大,边权是(100.0-c)/100
在求单源最短路时,Dijkstra 算法能够用当前没有使用的到源点的路径最短的点x来更新它出边连接的点y,是建立在两个基础上的:1.比它路径更短的点已经使用了。2.所有边权非负。
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N=2010,M=2e5+10;
int h[N],e[M],ne[M],idx;
bool st[N];
double w[M],dist[N];
int n,m,start,ed;
void add(int a,int b,int c){
e[idx]=b,w[idx]=(100.0-c)/100,ne[idx]=h[a],h[a]=idx++;
}
double spfa(){
dist[start]=1;
queue<int> q;
q.push(start);
st[start]=true;
while(q.size()){
auto t=q.front();
q.pop();
st[t]=false;
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]=true;
}
}
}
}
return dist[ed];
}
int main(){
cin>>n>>m;
memset(h,-1,sizeof h);
for(int i=0;i<m;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
cin>>start>>ed;
double t=spfa();
printf("%.8lf",100/t);
}