# Well Project

quoc14

c_cpp

15 days ago

2.4 kB

2

Indexable

Never

PrimDijktra

^{}

Level 3 Well Project Our company planned to help dig a well in a place in Africa which suffers from lack of water. After lots of research, we could dig the well full of water. After this success, we decided not only to dig the well but also to connect pipelines to towns scattered far from the well. Now your task is to connect all towns together with the well with the minimum length of pipelines. Find out the minimum pipeline length. Time limit : 1 sec (Java : 2 sec) [Input] There can be more than one test case in the input file. The first line has T, the number of test cases. Then the totally T test cases are provided in the following lines (T ≤ 10 ) In each test case, The size of the matrix (N) is given at the first row. (3 ≤ N ≤ 100) The distance information of each town is given from the second row to row of N. The information is the format of N×N matrix. jth number of ith row is the distance from ith town to jth town. The number on a diagonal line is always 0. [Output] For each test case, you should print "Case #T" in the first line where T means the case number. For each test case, you should output the minimum pipeline length to connect each town in the first row. [I/O Example] Input 2 3 0 1 4 1 0 2 4 2 0 4 0 4 9 21 4 0 8 17 9 8 0 16 21 17 16 0 Output Case #1 3 Case #2 28 Case #1 3433 Case #2 6043 Case #3 6061 Case #4 5831 Case #5 6922 Case #6 5337 Case #7 5822 Case #8 6070 Case #9 4830 Case #10 5656 #include <iostream> using namespace std; int T, n; long result; int mp[101][101]; bool vs[101]; void prim(){ for(int i = 0; i < n; i++) vs[i] = false; vs[0] = true; int selected = 1; while(selected < n){ int minV = LONG_MAX, minI; for(int i = 0; i < n; i++){ if(vs[i]){ for(int j = 0; j < n; j++){ if(!vs[j] && i != j){ if(minV > mp[i][j]){ minV = mp[i][j]; minI = j; } } } } } vs[minI] = true; selected++; result += minV; } } int main(){ freopen("input.txt", "r", stdin); cin >> T; for(int tc = 1; tc <= T; tc++){ // Input cin >> n; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++) cin >> mp[i][j]; } // Initial result = 0; // Solve Problem prim(); // Output cout << "Case #" << tc << endl << result << endl; } return 0; }

Leave a Comment