题目1343：城际公路网

题目1343：城际公路网

时间限制：1 秒

内存限制：32 兆

特殊判题：否

提交：562

解决：228

题目描述：

为了加快城市之间的通行和物资流动速度，A国政府决定在其境内的N个大中型城市之间，增加修建K条公路。已知这N个城市中的任意两个都能相互连通，且已知其最短的路径长度。为了时刻监测修建新路对A国城市的影响，特任命你为观察员，负责在每修建完一条公路之后，就向该国领导汇报当前N个城市间的最短路之和。

输入：

测试数据包括多个，每个测试数据包含四个部分 首先第一行将输入整数N，其中2 <= N <= 300，代表城市的个数。 第二部分是是一个N * N大小的整数矩阵，代表A国城市之间的一个最短路长度情况。矩阵的第i行，第j列代表从城镇i到城镇j的最短路d _ij的长度。输入数据保证当i == j时，d _ij  = 0；同时还保证d_ij = d_ji。 第三部分是一个整数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

答疑：

解题遇到问题?分享解题心得?讨论本题请访问： http://t.jobdu.com/thread-8066-1-1.html

这道题目开始看完后，直接就用了floyed，唉，写ACM真的要多想，才能找到特殊的方法

后来WA，问了学长，他帮我改进了floyed，只用了两层循环

就是只需要不断跟新与重修公路有关城市的路径，其他的不管

#include
#include
#include
#include
#include
#include
using namespace std;
#define maxn 1010
int mapn[305][305],vis[105][105];
int main()
{int n;while(~scanf("%d",&n)){for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)scanf("%d",&mapn[i][j]);int m;scanf("%d",&m);while(m--){int a,b,c;scanf("%d%d%d",&a,&b,&c);//mapn[a][b] = mapn[b][a] = c;//注意这里不需要直接跟新mapn，因为他重修的公路不一定是最短的for(int w=1; w<=n; w++){for(int m=1; m<=n; m++){if(mapn[w][m]>mapn[w][a]+c+mapn[b][m]){//在这里不断跟新与重修公路有关的城市的路径mapn[w][m]=mapn[w][a]+c+mapn[b][m];mapn[m][w]=mapn[w][m];}}}long long sum = 0;memset(vis,0,sizeof(vis));for(int i=1;i<=n;i++)for(int j=1;j){sum = sum + mapn[i][j];}printf("%lld\n",sum);}}return 0;
}

 

转载于:https://www.cnblogs.com/l609929321/p/6601777.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！