106 miles to Chicago
Time Limit:5000MS Memory Limit:32768KB 64bit IO Format:%lld & %lld
Description
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.
Input Specification
The input file 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 integersa,
b and p (1 ≤ a, b ≤ n , a ≠ b, 1 ≤ p ≤ 100):
a and b are the two end points of the street andp 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.
Output Specification
For each test case, calculate the probability of the safest path from intersection1 (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 intersection1 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.
Sample Input
5 7 5 2 100 3 5 80 2 3 70 2 1 50 3 4 90 4 1 85 3 1 70 0
Sample Output
61.200000 percent
Input
SpecificationThe input file 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 integersa,
b and p (1 ≤ a, b ≤ n , a ≠ b, 1 ≤ p ≤ 100):
a and b are the two end points of the street andp 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.
Output
SpecificationFor each test case, calculate the probability of the safest path from intersection1 (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 intersection1 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.
Sample Input
5 7 5 2 100 3 5 80 2 3 70 2 1 50 3 4 90 4 1 85 3 1 70 0
Sample Output
61.200000 percent
題目解析：
題目說給出m條邊，n個點。叫你求出其中可以組成的最長路。一道圖論的水題。居然比賽時候沒看該題沒做出來！！！真想說what fack are you doing!!!!說自己搞圖論的，到現在為止現場比賽中沒做出過一道圖論題。cao!!!
思路解析：
我們可以根據乘法原理知道，概率是相乘的，但是直接相乘的話，題中的數據會超int。所以，我們把他轉換成double先縮小倍數最後結果在乘回去，這個結果顯然是正確的。別的就是最長路的求法了，沒什麼可講的了。
下面給出三種不同的寫法。
/*
vector實現圖的存儲
*/
#include
#include
#include
#include
#include
#include
using namespace std;
const int N = 100+5;
struct Node
{
int to;
double d;
};
vector vet[N];
double SPFA(int s,int n)
{
queue q;
bool inq[N];
double dis[N];
for(int i = 0;i <= n;++i){
inq[i] = 0;
dis[i] = -1;
}
q.push(s);
dis[s] = 1;
inq[s] = 1; // printf("dis[n] = %lf\n",dis[n]);
while(!q.empty())
{
int v = q.front();
q.pop();
inq[v] = 0;
for(int i = 0;i < int(vet[v].size());++i){
int u = vet[v][i].to;
if(vet[v][i].d*dis[v] > dis[u]){
dis[u] = vet[v][i].d*dis[v]; // printf("dis[%d] = %lf \n",v,dis[v]);
if(!inq[u]){
inq[u] = 1;
q.push(u);
}
}
}
}
return dis[n];
}
int main()
{
int n,m,a,b;
while(scanf("%d",&n),n)
{
for(int i = 0;i <= n;++i)
vet[i].clear();
scanf("%d",&m);
for(int i = 0;i < m;i++){
double p;
Node node;
scanf("%d%d%lf",&a,&b,&p);
node.to = b;
node.d = p*0.01; //縮小倍數
vet[a].push_back(node);
node.to = a;
node.d = p*0.01;
vet[b].push_back(node);
}
double ans = SPFA(1,n);
printf("%.6lf percent\n",ans*100.0);
}
}
/* 鄰接表實現 */ #include#include #include #include #include #include #include using namespace std; const int N = 100+5; const double EPS = 1e-8; struct EDGE { int v,Next; double d; }edge[2*N*N]; int Head[2*N],E; void Add(int u,int v,double p) { edge[E].v = v; edge[E].d = p; edge[E].Next = Head[u]; Head[u] = E++; } double SPFA(int s,int n) { bool inq[N]; double dis[N]; queue q; memset(inq,0,sizeof(inq)); memset(dis,0,sizeof(dis)); q.push(s); dis[s] = 1; inq[s] = 1; while(!q.empty()) { int u = q.front(); q.pop(); inq[u] = 0; for(int i = Head[u];i != -1;i = edge[i].Next){ int v = edge[i].v; if(dis[u]*edge[i].d > dis[v]){ dis[v] = dis[u]*edge[i].d; if(!inq[v]){ inq[v] = 1; q.push(v); } } } } return dis[n]; } int main() { int m,n; while(scanf("%d",&n),n) { memset(Head,-1,sizeof(Head)); scanf("%d",&m); E = 0; for(int i = 0;i < m;++i) { int a,b; double p; scanf("%d%d%lf",&a,&b,&p); Add(a,b,p*0.01); Add(b,a,p*0.01); } double ans = SPFA(1,n); printf("%.6lf percent\n",ans*100.0); } return 0; }
/* Floy實現 */ #include#include #include #include #include using namespace std; const int N = 100 + 5; double graph[N][N]; int n,m; void Init() { for(int i = 0;i < N;++i) for(int j = 0;j < N;++j) graph[i][j] = 0; } void Floy() { for(int k = 1;k <= n;k++){ for(int i = 1;i <= n;i++){ if(i == k)continue; for(int j = 1;j <= n;j++){ if(j==k||j==i)continue; // if(graph[i][k]==0.0||graph[k][j]==0.0)continue; if(graph[i][j] < graph[i][k]*graph[k][j]) graph[i][j] = graph[i][k]*graph[k][j]; } } } } int main() { while(scanf("%d",&n),n) { Init(); scanf("%d",&m); for(int i = 0;i < m;++i){ int a,b; double p; scanf("%d%d%lf",&a,&b,&p); graph[a][b] = graph[b][a] = p*0.01; } Floy(); printf("%.6lf percent\n",graph[1][n]*100.0); } return 0; }
