求调(全RE)
查看原帖
求调(全RE)
1038014
guolingyi楼主2024/10/25 08:55
#include<bits/stdc++.h>
using namespace std;
int n,m;
double v[2001][2001];
vector<int> a[2000];
double dis[2100];
int b[2100];
int main()
{
    cin>>n>>m;
    memset(v,0x7f,sizeof(v));
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        v[x][y]=1-(z/100.00);
        v[y][x]=1-(z/100.00);
        a[x].push_back(y);
        a[y].push_back(x);
    }
    int A,B;
    cin>>A>>B;
    dis[A]=1;
    for(int i=1;i<=n;i++)
    {
        int minn=0;
        for(int j=1;j<=n;j++)
            if(!b[j]&&dis[minn]<dis[j])
                minn=j;
        b[minn]=1;
        for(int j=0;j<a[minn].size();j++)
        {
            int j1=a[minn][j];
            if(!b[j1]&&dis[j1]<dis[minn]*v[j1][minn])
            {
                dis[j1]=dis[minn]*v[j1][minn];
            }
        }
        
        
    }
    printf("%.8lf",100/dis[B]);
    return 0;
}
2024/10/25 08:55
加载中...