朴素版Dij
存图方式
每个点转移成100至少所需的百分比。
参考代码
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f
#define N 2005
int n,m;
int a,b;
int x,y,z;
bool vis[N];
double money[N][N];
double mon[N*N];
void dij() {
int sum=1,k;
while(sum<n) {
double minn=INF;
for(int i=1; i<=n; i++) {
if(!vis[i]&&mon[i]<minn) {
minn=mon[i];
k=i;
}
}
vis[k]=1;
sum++;
for(int i=1; i<=n; i++)
if(vis[i]==0&&mon[i]>mon[k]*money[k][i])
mon[i]=mon[k]*money[k][i];
}
}
int main() {
memset(money,127,sizeof(money));
for(int i=1; i<=n; i++)
money[i][i]=0;
scanf("%d%d",&n,&m);
for(int i=1; i<=m; i++) {
scanf("%d%d%d",&x,&y,&z);
money[x][y]=100.0/(100-z);
money[y][x]=100.0/(100-z);
}
scanf("%d%d",&a,&b);
vis[a]=1;
for(int i=1; i<=n; i++)
if(money[a][i])
mon[i]=money[a][i];
dij();
printf("%.8f",mon[b]*100);
}