炸學校?
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：”，然后是一個整數表示最少需要的時間。
示例輸入
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 #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 }
?
