2013
11-11

# 106 miles to Chicago

In the movie “Blues Brothers”, the orphanage where Elwood and Jack were raised may be sold to the Board of Education if they do not pay 5000 dollars in taxes at the Cook Country Assessor’s Office in Chicago. After playing a gig in the Palace Hotel ballroom to earn these 5000 dollars, they have to find a way to Chicago. However, this is not so easy as it sounds, since they are chased by the Police, a country band and a group of Nazis. Moreover, it is 106 miles to Chicago, it is dark and they are wearing sunglasses.

As they are on a mission from God, you should help them find the safest way to Chicago. In this problem, the safest way is considered to be the route which maximises the probability that they are not caught.

The input contains several test cases.

Each test case starts with two integers n and m (2 <= n <= 100 , 1 <= m <= n*(n-1)/2). n is the number of intersections, m is the number of streets to be considered.

The next m lines contain the description of the streets. Each street is described by a line containing 3 integers a, b and p (1 <= a, b <= n , a != b, 1 <= p <= 100): a and b are the two end points of the street and p is the probability in percent that the Blues Brothers will manage to use this street without being caught. Each street can be used in both directions. You may assume that there is at most one street between two end points.

The last test case is followed by a zero.

For each test case, calculate the probability of the safest path from intersection 1 (the Palace Hotel) to intersection n (the Honorable Richard J. Daley Plaza in Chicago). You can assume that there is at least one path between intersection 1 and n.

Print the probability as a percentage with exactly 6 digits after the decimal point. The percentage value is considered correct if it differs by at most 10-6 from the judge output. Adhere to the format shown below and print one line for each test case.

5 7
5 2 100
3 5 80
2 3 70
2 1 50
3 4 90
4 1 85
3 1 70
0


61.200000 percent


//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;

public class Main {
static int N = 100+5;

static int n;
static double Graph[][] = new double[N][N];
public static void init(){
int i,j;
for(i=0;i< N;++i) for(j=0;j< N;++j)
Graph[i][j] = 0.0;
}

public static void main(String args[]) throws Exception{

double temp;
int i,j,u,v,m;
//Scanner cin = new Scanner(new FileInputStream("input.txt"));
Scanner cin = new Scanner(System.in);

while(cin.hasNext()){
n = cin.nextInt();
if(n==0) break;

init();

m = cin.nextInt();
for(i=0;i< m;++i){
u = cin.nextInt();
v = cin.nextInt();
temp = cin.nextDouble();
Graph[v][u] = Graph[u][v] = temp/100.0;
}

temp = dijkstra()*100;
System.out.printf("%.6f", temp);
System.out.println(" percent");
}
}

public static double dijkstra(){
int i,j,k;
boolean flag[] = new boolean[N];
double meat[] = new double[N];

for(i=1;i<=n;++i) {
meat[i] = Graph[1][i];
flag[i] = false;
}
flag[1] = true;

for(i=0;i< n;++i){
k = -1;
for(j=1;j<=n;++j) if(!flag[j]){
if(k==-1 || meat[k]< meat[j])
k = j;
}
if(k==-1) break;
flag[k] = true;

for(j=1;j<=n;++j)if(!flag[j]){
if(meat[j]< meat[k]*Graph[k][j])
meat[j] = meat[k]*Graph[k][j];
}
}
return meat[n];
}
}

1. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1))；因为第二种解法如果数组有重复元素 就不正确

2. 如果两个序列的最后字符不匹配（即X [M-1]！= Y [N-1]）
L（X [0 .. M-1]，Y [0 .. N-1]）= MAX（L（X [0 .. M-2]，Y [0 .. N-1]），L（X [0 .. M-1]，Y [0 .. N-1]）
这里写错了吧。

3. for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
dp = dp [j-1] + 1;
if(s1.charAt(i-1) == s3.charAt(i+j-1))
dp = dp[i-1] + 1;
if(s2.charAt(j-1) == s3.charAt(i+j-1))
dp = Math.max(dp [j - 1] + 1, dp );
}
}
这里的代码似乎有点问题？ dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false

4. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。

5. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.