首页 > 代码库 > SDUT3034--炸学校（最短路）
SDUT3034--炸学校（最短路）
炸学校
Time Limit: 2000ms Memory limit: 65536K 有疑问？点这里^_^
题目描述
“小儿么小二郎，背着那炸弹炸学校，不怕那太阳晒，也不怕那风雨狂。”估计这首歌我们大家都耳熟能详了。
于是就有一群小学生们商量着炸学校。要把本市的小学的都给炸掉。于是他们商量好了一个出发点source与集合点sink。然后有无数个小学生，n-2个学校，每个小学生都从出发点出发，负责背着一个炸弹，然后把炸弹偷偷放置在一个学校里，然后返回到集合点。
于是就有一群小学生们商量着炸学校。要把本市的小学的都给炸掉。于是他们商量好了一个出发点source与集合点sink。然后有无数个小学生，n-2个学校，每个小学生都从出发点出发，负责背着一个炸弹，然后把炸弹偷偷放置在一个学校里，然后返回到集合点。
由于这群小学生们还急着回去玩撸啊撸，所以他们想尽快把所有学校都炸完。这里有m条无向路，每条路都连接着u和v这两个学校，经过这条路的时间花费为t。这些小学生只能从这些路中经过。他们同时从出发点出发，他们想知道炸完所有学校并且都回到集合点的最少需要多长时间。
输入
第一行为一个整数T，表示T组测试数据。
第二行为整数n（3<=n<=1000），代表学校的数量（包括出发点和集合点），还有整数m（m<10^5），表示有多少条无向路。
然后接下来是m行，每一行的三个整数分别是u，v，t（0<=u，v， u！=v， 0<=t<=10^5）
然后给出两个整数source和sink，分别代表出发点和集合点。（0<=source，sink）。
输入数据保证可以炸毁所有学校，并且可以到达集合点。不保证没有重边。
输出：
输出
对于第x组数据输出一行“Case #x：”，然后是一个整数表示最少需要的时间。
示例输入
15 51 0 11 2 31 3 34 2 23 4 14 2
示例输出
Case #1: 9
题意：设一个起点和一个终点，一群小学生（>=n）,他们分别从起点出发，然后每个人都背着炸药去炸学校，炸完后再回到终点，求最短时间。
注意：他们是同时出发。
可以这样求，假设起点和终点分别为（x,y）,则以x为起点求到其它点的最短路径，存起来。然后再以y为起点，求到其它点的最短路径。
求完后把到相同点的最短路径加起来，假设值为D，则要求最大的一个D，因为只有这样，才可以满足条件使每个小学生都可以把学校炸了。
1 #include<stdio.h> 2 #include<string.h> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 7 int T, n, m; 8 const int maxnum = 1002; 9 const int maxint = 1000000;10 11 int dis[maxnum], p[maxnum];//最短路径数组12 int mapp[maxnum][maxnum];//建图13 14 void init() //初始化mapp数组15 {16 int i, j;17 for(i=0; i<n; i++)18 {19 for(j=0; j<n; j++)20 {21 if(i!=j)22 mapp[i][j] = maxint;23 else mapp[i][j] = 0;24 }25 }26 }27 28 void Dijkstra(int x, int y) //dijkstra最短路算法29 {30 bool vis[maxnum];31 int i;32 for(i=0; i<n; i++){33 dis[i] = mapp[x][i];34 vis[i] = 0;35 }36 dis[x] = 0;37 vis[x] = 1;38 39 for(i=2; i<=n; i++){40 int tmp = maxint;41 int pos = 1;42 for(int j=0; j<n; j++)43 if((!vis[j]) && dis[j]<tmp && j!=x){44 pos = j;45 //printf("pos = %d\n", pos);46 tmp = dis[j];47 }48 vis[pos] = 1;49 50 for(int j=0; j<n; j++)51 if((!vis[j]) && mapp[pos][j] < maxint)52 {53 int newdis = dis[pos] + mapp[pos][j];54 if(newdis < dis[j])55 {56 dis[j] = newdis;57 }58 }59 }60 for(i=0; i<n; i++)61 {62 p[i] += dis[i];63 }64 }65 66 int main()67 {68 69 int x, y, c, i, k=1;70 scanf("%d", &T);71 while(T--)72 {73 scanf("%d%d", &n, &m);74 memset(p, 0, sizeof(p));75 init();76 for(i=0; i<m; i++)77 {78 scanf("%d%d%d", &x, &y, &c);79 if(mapp[x][y]>c) //有重边的情况80 {81 mapp[x][y] = c;82 mapp[y][x] = c;83 }84 }85 scanf("%d%d", &x, &y);86 Dijkstra(x, y);87 Dijkstra(y, x);88 sort(p, p+n);89 printf("Case #%d: %d\n",k++, p[n-1]);90 }91 return 0;92 }
SDUT3034--炸学校（最短路）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。