西安长安区网站优化地址,仿网站后台怎么做,wordpress电脑主题,深圳公关公司首荐乐云seo炸学校 Time Limit: 2000ms Memory limit: 65536K 有疑问#xff1f;点这里^_^ 题目描述 “小儿么小二郎#xff0c;背着那炸弹炸学校#xff0c;不怕那太阳晒#xff0c;也不怕那风雨狂。”估计这首歌我们大家都耳熟能详了。于是就有一群小学生们商量着炸学校。要把本… 炸学校 Time Limit: 2000ms Memory limit: 65536K 有疑问点这里^_^ 题目描述 “小儿么小二郎背着那炸弹炸学校不怕那太阳晒也不怕那风雨狂。”估计这首歌我们大家都耳熟能详了。于是就有一群小学生们商量着炸学校。要把本市的小学的都给炸掉。于是他们商量好了一个出发点source与集合点sink。然后有无数个小学生n-2个学校每个小学生都从出发点出发负责背着一个炸弹然后把炸弹偷偷放置在一个学校里然后返回到集合点。 由于这群小学生们还急着回去玩撸啊撸所以他们想尽快把所有学校都炸完。这里有m条无向路每条路都连接着u和v这两个学校经过这条路的时间花费为t。这些小学生只能从这些路中经过。他们同时从出发点出发他们想知道炸完所有学校并且都回到集合点的最少需要多长时间。 输入 第一行为一个整数T表示T组测试数据。 第二行为整数n3n1000代表学校的数量包括出发点和集合点还有整数mm10^5表示有多少条无向路。 然后接下来是m行每一行的三个整数分别是uvt0uv uv 0t10^5 然后给出两个整数source和sink分别代表出发点和集合点。0sourcesink。 输入数据保证可以炸毁所有学校并且可以到达集合点。不保证没有重边。 输出 输出 对于第x组数据输出一行“Case #x”然后是一个整数表示最少需要的时间。 示例输入 1
5 5
1 0 1
1 2 3
1 3 3
4 2 2
3 4 1
4 2 示例输出 Case #1: 9题意设一个起点和一个终点一群小学生n,他们分别从起点出发然后每个人都背着炸药去炸学校炸完后再回到终点求最短时间。注意他们是同时出发。 可以这样求假设起点和终点分别为x,y,则以x为起点求到其它点的最短路径存起来。然后再以y为起点求到其它点的最短路径。求完后把到相同点的最短路径加起来假设值为D则要求最大的一个D因为只有这样才可以满足条件使每个小学生都可以把学校炸了。 1 #includestdio.h2 #includestring.h3 #includeiostream4 #includealgorithm5 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(i0; in; i)
18 {
19 for(j0; jn; 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(i0; in; i){
33 dis[i] mapp[x][i];
34 vis[i] 0;
35 }
36 dis[x] 0;
37 vis[x] 1;
38
39 for(i2; in; i){
40 int tmp maxint;
41 int pos 1;
42 for(int j0; jn; 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 j0; jn; 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(i0; in; i)
61 {
62 p[i] dis[i];
63 }
64 }
65
66 int main()
67 {
68
69 int x, y, c, i, k1;
70 scanf(%d, T);
71 while(T--)
72 {
73 scanf(%d%d, n, m);
74 memset(p, 0, sizeof(p));
75 init();
76 for(i0; im; 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, pn);
89 printf(Case #%d: %d\n,k, p[n-1]);
90 }
91 return 0;
92 } 转载于:https://www.cnblogs.com/6bing/p/4135660.html
