UVa 821 Page Hopping

Floyd 알고리즘을 이용하면 쉽게 풀릴듯..

2000년 ACM World Final 중에서 가장 높은 정답률을 보인 문제

문제 링크

코드

view plaincopy to clipboardprint?

1. #include <iostream> 
2. #include <cstdlib> 
3. #include <list> 
4.  
5. using namespace std;  
6.  
7. #define INFINITE 1000 
8.  
9. unsigned int pageGraph[101][101];  
10. bool usedPage[101];  
11. list<unsigned int> usedPageList;  
12.  
13. int main()  
14. {  
15.     unsigned int pairs[2];  
16.  
17.     int count = 1;  
18.     int sum = 0;  
19.     float average = 0.0;  
20.     while( cin >> pairs[0] >> pairs[1])  
21.     { 
22.         if(pairs[0] == 0 && pairs[1] == 0)  
23.         { 
24.             break;  
25.         } 
26.         // graph 초기화 
27.         for(int i = 0; i < 101; i++)  
28.         { 
29.             for(int j = 0; j < 101; j++)  
30.             { 
31.                 pageGraph[i][j] = INFINITE;  
32.             } 
33.         } 
34.         //memset(pageGraph, , sizeof(pageGraph)); 
35.         memset(usedPage, false, sizeof(usedPage));  
36.         usedPageList.clear();  
37.         sum = 0;  
38.         average = 0.0;  
39.  
40.         // graph 생성 
41.         do{  
42.             if(pairs[0] == 0 && pairs[1] == 0)  
43.             { 
44.                 break;  
45.             } 
46.             usedPage[pairs[0]] = true;  
47.             usedPage[pairs[1]] = true;  
48.             pageGraph[pairs[0]][pairs[1]] = 1;  
49.              
50.         } 
51.         while( cin >> pairs[0] >> pairs[1]);  
52.  
53.          
54.         for(int i= 1; i <= 100; i++ ) 
55.         { 
56.             if(usedPage[i])  
57.             { 
58.                 usedPageList.push_back(i);  
59.             } 
60.         } 
61.  
62.         //floyd algorithm 
63.         list<unsigned int>::iterator it_i, it_j, it_k;  
64.         for(it_i = usedPageList.begin(); it_i != usedPageList.end(); ++it_i)  
65.         //it_i를 거쳐서 가는경우 
66.         { 
67.             for(it_j = usedPageList.begin(); it_j != usedPageList.end(); ++it_j)  
68.             { 
69.                 for(it_k = usedPageList.begin(); it_k != usedPageList.end(); ++it_k)  
70.                 { 
71.                     if(pageGraph[*it_j][*it_i] != INFINITE && pageGraph[*it_i][*it_k] != INFINITE  
72.                         && *it_j != *it_i && *it_k != *it_i && *it_j != *it_k)  
73.                     { 
74.                         if(pageGraph[*it_j][*it_i] + pageGraph[*it_i][*it_k] < pageGraph[*it_j][*it_k])  
75.                         { 
76.                             pageGraph[*it_j][*it_k] = pageGraph[*it_j][*it_i] + pageGraph[*it_i][*it_k];  
77.                         } 
78.                     } 
79.                      
80.                 } 
81.             } 
82.         } 
83.  
84.         for(it_i = usedPageList.begin(); it_i != usedPageList.end(); ++it_i)  
85.         { 
86.             for(it_j = usedPageList.begin(); it_j != usedPageList.end(); ++it_j)  
87.             { 
88.                 if(pageGraph[*it_i][*it_j] != INFINITE)  
89.                 { 
90.                     sum += pageGraph[*it_i][*it_j];  
91.                 } 
92.             } 
93.         } 
94.  
95.         average = (float)sum / (usedPageList.size()*(usedPageList.size()-1));  
96.         printf("Case %d: average length between pages = %.3f clicks\n",  
97.                 count, average);  
98.         count++;  
99.     } 
100.  
101.     return 0;  
102. }