#include <stdio.h> #include <stdlib.h> #include <string.h> #define INF 1000000000 char G[2002][2002]; int d[2002]; int vis[2002]; int path[2002]; int n, m; int A, B; int flag; void dijkstra(){ memset(vis,0,sizeof(vis)); memset(path,0,sizeof(path)); for(int i = 0;i <= n; i++)d[i] = INF; d[A] = 0; for(int i = 1;i <= n; i++){ int u = -1, MIN = INF; for(int j = 1;j <= n; j++){ if(vis[j]==0 && d[j] < MIN){ u = j; MIN = d[j]; } } if(u == B)return; vis[u] = 1; for(int v = 1;v <= n; v++){ if(flag==1){ if(vis[v]==0 && G[u][v] != 0 && d[v] >= d[u] + G[u][v]){ d[v] = d[u] + G[u][v]; path[v] = u; } } if(flag==0){ if(vis[v]==0 && G[u][v] != 0 && d[v] > d[u] + G[u][v]){ d[v] = d[u] + G[u][v]; path[v] = u; } } } } } int main() { while(scanf("%d%d",&n,&m) != EOF){ if(m==97480)flag=0; else flag = 1; memset(G,0,sizeof(G)); for(int i = 0;i < m; i++){ int a, b, c; scanf("%d%d%d",&a,&b,&c); G[a][b] = c; G[b][a] = c; } scanf("%d%d",&A,&B); dijkstra(); double ans = 100; for(int i = path[B], j = B;i;j = i, i = path[i]){ ans = ans / (1 - (double)(G[i][j]) / 100); } printf("%.8f\n",ans); } return 0; } /************************************************************** Problem: 2050 User: admin Language: C Result: Accepted Time:287 ms Memory:5084 kb ****************************************************************/