nyoj 115-城市平乱 (BFS) 115-城市平乱

内存限制:64MB 时间限制:1000ms 特判: No
通过数:5 提交数:8 难度:4

题目描述:

南将军统领着N个部队，这N个部队分别驻扎在N个不同的城市。

他在用这N个部队维护着M个城市的治安，这M个城市分别编号从1到M。

现在，小工军师告诉南将军，第K号城市发生了*，南将军从各个部队都派遣了一个分队沿最近路去往*城市平乱。

现在已知在任意两个城市之间的路行军所需的时间，你作为南将军麾下最厉害的程序员，请你编写一个程序来告诉南将军第一个分队到达*城市所需的时间。

nyoj 115-城市平乱 (BFS)
115-城市平乱

注意，两个城市之间可能不只一条路。

输入描述:

第一行输入一个整数T，表示测试数据的组数。(T<20)
每组测试数据的第一行是四个整数N,M,P,Q(1<=N<=100,N<=M<=1000,M-1<=P<=100000)其中N表示部队数，M表示城市数，P表示城市之间的路的条数,Q表示发生*的城市编号。
随后的一行是N个整数，表示部队所在城市的编号。
再之后的P行，每行有三个正整数，a,b,t(1<=a,b<=M,1<=t<=100)，表示a,b之间的路如果行军需要用时为t

数据保证*的城市是可达的。

输出描述:

对于每组测试数据，输出第一支部队到达*城市时的时间。每组输出占一行

样例输入:

样例输出:

C/C++:

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <cstdio>
 5 #include <cmath>
 6 #include <stack>
 7 #include <set>
 8 #include <map>
 9 #include <queue>
10 #include <climits>
11 #include <bitset>
12 #define eps 1e-6
13 using namespace std;
14 
15 int n, m, p, q, my_book[1010], my_map[1010][1010];
16 
17 struct node
18 {
19     bool has_army;
20     int cnt;
21 }my_army[1010];
22 
23 int bfs()
24 {
25     int my_ans = INT_MAX, q1;
26     queue <int> Q;
27     Q.push(q);
28     my_book[q] = 1;
29     while (!Q.empty())
30     {
31         q1 = Q.front();
32         for (int i = 1; i <= m; ++ i)
33         {
34             if (my_book[i] || !my_map[q1][i]) continue;
35             my_book[i] = 1;
36             my_army[i].cnt = my_army[q1].cnt + my_map[q1][i];
37             Q.push(i);
38             if (my_army[i].has_army && my_army[i].cnt < my_ans) my_ans = my_army[i].cnt;
39         }
40         Q.pop();
41     }
42     return my_ans;
43 }
44 
45 int main()
46 {
47     ios::sync_with_stdio(false);
48     int t;
49     scanf("%d", &t);
50     while (t --)
51     {
52         /**
53             initialize
54         */
55         memset(my_army, 0, sizeof (my_army));
56         memset(my_book, 0, sizeof (my_book));
57         memset(my_map, 0, sizeof (my_map));
58 
59         /**
60             Date input
61         */
62         scanf("%d%d%d%d",&n, &m, &p, &q);
63         for (int i = 0; i < n; ++ i)
64         {
65             int temp;
66             scanf("%d", &temp);
67             my_army[temp].has_army = true;
68         }
69         for (int i = 0; i < p; ++ i)
70         {
71             int a, b, a_b_distance;
72             scanf("%d%d%d", &a, &b, &a_b_distance);
73             my_map[a][b] = my_map[b][a] = a_b_distance;
74         }
75 
76         /**
77             get answer
78         */
79         printf("%d
", bfs());
80     }
81 
82     return 0;
83 }