题解 P1576 【最小花费】

蒟蒻的第一篇题解竟然是Dijkstra

翻来覆去总不明白为什么楼下大佬要用堆优化---

无脑

很简单的一道luo -D ijk str a- 题目啊！

贴代码贴代码——

#include<iostream>
#include<cmath>
#include<iomanip>
#define maxn 0x7fffffff
using namespace std;
int n,m,get[2001],p[2001],a1,a2;
double bj[2001][2001],d[2001];
void dijkstra()
{
    d[a1]=100;p[a1]=a1;
    for(int i=1;i<=n;i++)
    {
        int ma=-maxn,k;
        for(int j=1;j<=n;j++)
            if(!get[j]&&ma<d[j]) ma=d[j],k=j;
        get[k]=1;
        for(int j=1;j<=n;j++)
            if(bj[k][j]&&!get[j]&&d[k]*bj[k][j]>d[j]) d[j]=d[k]*bj[k][j],p[j]=k;
    }
}
int main()
{
    int qw,er,ty;
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>qw>>er>>ty,bj[er][qw]=bj[qw][er]=(100.0-ty)/100;
    cin>>a2>>a1;
    dijkstra();
    cout<<fixed<<setprecision(8)<<100.0/d[a2]*100<<endl;
}

声明：p[2001]标记father是为了方便需要输出路径的-题用，此题请无视

-DaLao请无视-