题解 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请无视-