首页 > 代码库 > 地铁规划
地铁规划
地铁，其优势在于覆盖面广方便出行。某城市考虑在全市修建地铁。目前已确定各大地铁站点，并预估两两站点之间修建地铁的成本。政府部门希望能尽可能地节省开支，同时也希望本次项目可以覆盖到全市各大站点，目前亟需一份相关的成本预算。你可以计算出该项目的最小成本吗？
可能有多个测试输入，第一行给出总共的测试输入的个数。
对于每个测试输入，第一行包含一个正整数N，接下来是N行铁道信息。每一行有N个整数X(0<N<100,0<X<10000),表示站点A和站点B之间修建地铁的成本为X。其中各站点到自身的成本视为0。
输出一个整数，即地铁项目的最小成本。
Sample Input
2
3
0 1 100
1 0 2
100 2 0
4
0 2 3 4
2 0 4 1
3 4 0 5
4 1 5 0
sampleoutput
3
6
这道题用了最小生成树prim算法（我也是看了题解才会的）
prim算法就是选取一个点，然后找到距离这个点权值最小的下一个点（这道题我是先选站点1作为第一个点，因为循环比较好写，但是也可以选其它点作为起点，权值的意思就是选距离选定点的最短路径的那个点，如果有两个点距离相同，那么选择站点数较小的那个点），然后在把下一个点作为选定点，以此类推，直到把所有的站点都包括进来。注意我们要找的最小值是已经选定的点到未选定的点的最小值。
那测例2来说明就是：当前存在4个站点，我们选站点1作为起点，此时最短路径为0，发现站点1到站点2的距离最短，所以我们选取站点2作为下一个点，此时最短路径为2。因此站点2是也是选定点，然后我们发现站点1,站点2（已经选定的点）中到站点3,站点4（还没有选的点）的最短路径是站点2到站点4，所以我们把站点4作为选定点，此时最短路径为3，最后我们发现1,2,4到3的最短路径是1到3，所以最后把3作为选定点，最短路径为6，此时我们发现所有点都被选定了，因此证明所有的点都有路径经过，所以输出最短路径6。
最后贴上代码。。。。
1 #include <iostream> 2 #include <cstdlib> 3 #include <cstring> 4 #include <cstdio> 5 // 感谢这位大牛的博客 6 //http://www.cnblogs.com/Veegin/archive/2011/04/29/2032388.html 7 using namespace std; 8 9 int main () {10 int T;11 cin >> T;12 while (T--) {13 int N;14 cin >> N;15 int road[N][N];16 int low[N]; 17 for (int i = 0; i < N; i++) {18 for (int j = 0; j < N; j++) { 19 scanf("%d", &road[i][j]);20 }21 low[i] = road[0][i];22 }23 int i, j,pos, res = 0, min;24 int visited[N];25 memset(visited, 0, sizeof(visited));26 visited[0] = 0; // 从A点开始标记 27 pos = 0; // 记录该点 28 for (i = 0; i < N; i++) { // 通过循环找到该行最小的距离 执行n - 1 次 29 min = 10000; // 把min设置成最大的 30 for (j = 0; j < N; j++) {31 if (visited[j] == 0 && min > low[j]) {32 min = low[j];33 pos = j;34 }35 }36 res += min; // 累加最小权重 37 visited[pos] = 1; // 说明pos所在的站已经有线路通过了 38 for (j = 0; j < N; j++) {39 if (visited[j] == 0 && low[j] > road[pos][j]) // 这个是通过已经找到的pos的那行去找还没有经过的站点的最小值 40 low[j] = road[pos][j];41 }42 }43 cout << res << endl;44 }45 system("pause");46 }
地铁规划