记录编号	97449	评测结果	AAAAAAAAAA
题目名称	[HAOI 2009]旅行	最终得分	100
用户昵称	麦田之上	是否通过	通过
代码语言	C++	运行时间	0.075 s
提交时间	2014-04-18 21:11:18	内存使用	1.77 MiB

#include <fstream>
#include <iomanip>
using namespace std;
int n,m,u=0;
int a[10005],que[10005],lin[60005],pred[60005],i,j,jj,t1,t2;
double chance[60005],c[60005],temp;
bool isin[10005];
int main()
{	ifstream fin("toura.in");
	ofstream fout("toura.out");
	fin>>n>>m;
        for (i=0;i<m;++i)
        {  t1,t2;
           ++u;
           fin>>t1>>t2>>chance[u];
           lin[u]=t2;
           pred[u]=a[t1];
           a[t1]=u;
           chance[u]=chance[u]*0.01;
           ++u;
           lin[u]=t1;
           pred[u]=a[t2];
           a[t2]=u;
           chance[u]=chance[u-1];
        }
    int h=1,t=2;
    que[1]=1;
    c[1]=1; 
    isin[1]=true;
    while (h!=t)
    {
          jj=que[h];
          i=a[jj];
          isin[jj]=false;
          while (i>0)
          {
                temp=c[jj]*chance[i];
                j=lin[i];
                if (temp>c[j])
                {
                              c[j]=temp;
                              if (!isin[j])
                              { que[t]=j;
                                isin[j]=true;
                                if (t==10005) {t=1;}
                                       else{++t;}
                               }
                }
                i=pred[i];
            }
            if (h==10005){h=1;}
                 else{++h;}
     }
   fout<<fixed<<setprecision(6)<<c[n]*100<<endl;
   fin.close();
   fout.close();
   return 0;        
}