Problem Statement
    
In the Republic of Nlogonia there are N cities. For convenience, the cities are numbered 0 through N-1. For each two different cities i and j, there is a direct one-way road from i to j. You are given the lengths of those roads as a vector <string> dist with N elements, each with N characters. For each i and j, the character dist[i][j] represents the length of the road from i to j. The lengths of roads are integers between 1 and 9, inclusive, and they are represented by digits ‘1‘ through ‘9‘. That is, for distinct i and j, dist[i][j] will be between ‘1‘ and ‘9‘. For each i, dist[i][i] will be ‘0‘. Note that the roads from i to j and from j to i may have different lengths. Every year on Algorithms Day (the most important holiday in Nlogonia) people travel between the cities. More precisely, for each pair of distinct cities i and j, one full bus of people travels from i to j. Each of those buses drives along a shortest path from its origin to its destination. If there are multiple shortest paths, the bus driver picks one of them arbitrarily. The roads in Nlogonia are currently limited. You are given an int T with the following meaning: each of the current roads is only safe if it is guaranteed that there will be strictly fewer than T buses driving along the road. In other words, a road is unsafe if it is possible that T or more buses will use it. The government wants to rebuild all unsafe roads before the next Algorithms Day. Return the sum of lengths of all unsafe roads.
Definition
    
Class:
BuildingRoutes
Method:
build
Parameters:
vector <string>, int
Returns:
int
Method signature:
int build(vector <string> dist, int T)
(be sure your method is public)
Limits
    
Time limit (s):
2.000
Memory limit (MB):
256
Constraints
-
N will be between 2 and 50, inclusive.
-
dist will contain exactly N elements.
-
Each element of dist will contain exactly N characters.
-
For each i, dist[i][i] will be ‘0‘.
-
For each pair of distinct i and j, dist[i][j] will be between ‘1‘ and ‘9‘, inclusive.
-
T will be between 1 and 2500, inclusive.
Examples
0)

    
{"011",
"101",
"110"}
1
Returns: 6
As T=1, a road is unsafe as soon as it is possible that a bus will use it. Each of the six roads in this test case belongs to some shortest path, hence each of them is unsafe
1)

    
{"033",
"309",
"390"}
1
Returns: 12
The roads 1->2 and 2->1 (the two roads of length 9) will not be used by any bus. Only the four remaining roads are unsafe in this case.
2)

    
{"0123",
"1023",
"1203",
"1230"}
2
Returns: 5

3)

    
{"05789654",
"10347583",
"65085479",
"55602398",
"76590934",
"57939045",
"12345608",
"68647640"}
3
Returns: 40

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "cstdlib"
 5 #include "cmath"
 6 #include "algorithm"
 7 #include "vector"
 8 #include "list"
 9 #include "map"
10 #include "queue"
11 #include "set"
12 #include "stack"
13 using namespace std;
14 
15 #define mset(a) memset(a,0,sizeof(a))
16 
17 class BuildingRoutes{
18 public:
19     int g[51][51], d[51][51], cnt[51][51], n, ans;
20 
21     void floyd(){
22         for(int k = 0; k < n; k++){
23             for(int i = 0; i < n; i++){
24                 for(int j = 0; j < n; j++){
25                     d[i][j] = min(d[i][k]+d[k][j], d[i][j]);
26                 }
27             }
28         }
29     }
30 
31     void run(int t){
32         mset(cnt);
33         for(int i = 0; i < n; i++){
34             for(int j = 0; j < n; j++){
35                 for(int x = 0; x < n; x++){
36                     for(int y = 0; y < n; y++){
37                         if(d[x][y] == d[x][i]+g[i][j]+d[j][y])
38                             cnt[i][j]++;
39                     }
40                 }
41             }
42         }
43         for(int i = 0; i < n; i++){
44             for(int j = 0; j < n; j++){
45                 if(cnt[i][j] >= t)
46                     ans += g[i][j];
47             }
48         }
49     }
50 
51     int build(vector <string> dist, int T){
52         n = dist[0].size();
53         for(int i = 0; i < n; i++){
54             for(int j = 0; j < n; j++){
55                 g[i][j] = dist[i][j]-‘0‘;
56                 d[i][j] = g[i][j];
57             }
58         }
59         floyd();
60         ans = 0;
61         run(T);
62         return ans;
63     }
64 };

View Code