时间限制：1 秒
内存限制：32 兆
特殊判题：否
提交：445
解决：178
- 题目描述：
- 为了加快城市之间的通行和物资流动速度，A国*决定在其境内的N个大中型城市之间，增加修建K条公路。已知这N个城市中的任意两个都能相互连通，且已知其最短的路径长度。为了时刻监测修建新路对A国城市的影响，特任命你为观察员，负责在每修建完一条公路之后，就向该国领导汇报当前N个城市间的最短路之和。
- 输入：
-
测试数据包括多个，每个测试数据包含四个部分首先第一行将输入整数N，其中2 <= N <= 300，代表城市的个数。第二部分是是一个N * N大小的整数矩阵，代表A国城市之间的一个最短路长度情况。矩阵的第i行，第j列代表从城镇i到城镇j的最短路dij的长度。输入数据保证当i == j时，dij = 0；同时还保证dij = dji。第三部分是一个整数K，1 <= K <= 300， 即计划修建的公路数量。第四部分包括K行，每行由三个整数a、b、w组成，整数之间由空格隔开。其中a、b代表城镇的编号（1 <= a、b <= N）, w为该条公路的长度（1 <= w<=1000）。注意：所建公路都为双向公路。
- 输出：
- 对于每个测试案例，输出K行，即修建了公路之后的N个城市的最短路径之和。例如，第i行则代表修建完1、2、3 …、i条公路之后的城市最短路径之和。
- 样例输入：
-
2
0 7
7 0
1
1 2 3
3
0 4 5
4 0 9
5 9 0
2
2 3 8
1 2 1
- 样例输出：
-
3
17
12
思路：
笨办法，每修完一条路之后求一遍最小生成树，然后求最短路径之和。
代码：
#include <stdio.h> #define N 300 int Min(int a, int b)
{
return (a<b) ? a : b;
} int main(void)
{
int n, k, i, j, r;
int a, b, w;
int map[N+1][N+1];
int sum; while (scanf("%d", &n) != EOF)
{
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
scanf("%d", &map[i][j]);
}
} scanf("%d", &k);
for (r=0; r<k; r++)
{
scanf("%d%d%d", &a, &b, &w);
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
map[i][j] = map[j][i] = Min(map[i][a]+w+map[b][j], map[i][j]);
}
}
sum = 0;
for(i=1; i<=n; i++)
{
for(j=i+1; j<=n; j++)
{
sum += map[i][j];
}
}
printf("%d\n", sum);
}
} return 0;
}
/**************************************************************
Problem: 1343
User: liangrx06
Language: C
Result: Accepted
Time:220 ms
Memory:1196 kb
****************************************************************/