这是一道最短路的裸题，但从寒假开始做，暑假才通过，可以看出有两点不足
1.态度不端正，有题没有过应该非常着急的去把它完成，如果是抱着学知识的态度，就不会去着急得刷太多的题目，而是静下心来，一道一道做。
2.不细心，即使到了暑假，也是调了很久。把pair<double,int>写成pair<int,double>，建成小根堆，一是对板子不熟悉，二是一个一直有的毛病，写代码不动脑子，凭感觉。脑子是个好东西~
但也有收获，比如又熟悉了一遍Dijkstra的板子，还有要建立一个超级源点或者都加入队列（本题用不上）
1 #include<iostream> 2 #include<cstdio> 3 #include<queue> 4 using namespace std; 5 int n,m,A,B,num; 6 struct Edge{ 7 int next,to; 8 double dis; 9 }edge[200007]; 10 int head[2007]; 11 double d[2007]; 12 bool vis[2007]; 13 typedef pair<double,int>pii; 14 priority_queue<pii,vector<pii> >Q; 15 void add(int from,int to,double d){ 16 edge[++num].next=head[from]; 17 edge[num].to=to; 18 edge[num].dis=d; 19 head[from]=num; 20 } 21 int main(){ 22 cin>>n>>m; 23 for(int i=1;i<=m;i++){ 24 int u,v;double w;cin>>u>>v>>w; 25 w = (100-w)*0.01; 26 add(u,v,w); 27 add(v,u,w); 28 } 29 cin>>A>>B; 30 for(int i=1;i<=n;i++){ 31 d[i]=0; 32 } 33 d[A]=1; 34 for(int i=1;i<=n;i++) 35 if(i!=A) Q.push(make_pair(0,i)); 36 Q.push(make_pair(1,A)); 37 while(!Q.empty()){ 38 int u=Q.top().second;Q.pop(); 39 if(vis[u]) continue; 40 vis[u]=true; 41 for(int i=head[u];i;i=edge[i].next){ 42 int v=edge[i].to; 43 if(vis[v]) continue; 44 if(d[v]<d[u]*edge[i].dis) { 45 d[v]=d[u]*edge[i].dis; 46 Q.push(make_pair(d[v],v)); 47 } 48 } 49 } 50 printf("%.8lf",100/d[B]); 51 return 0; 52 } 53 54 //A最小->100/w,w要尽可能大->最长路