1174 - Commandos
InputA group of commandos were assigned a critical task. They are to destroy an enemy head quarter. The enemy head quarter consists of several buildings and the buildings are connected by roads. The commandos must visit each building and place a bomb at the base of each building. They start their mission at the base of a particular building and from there they disseminate to reach each building. The commandos must use the available roads to travel between buildings. Any of them can visit one building after another, but they must all gather at a common place when their task in done. In this problem, you will be given the description of different enemy headquarters. Your job is to determine the minimum time needed to complete the mission. Each commando takes exactly one unit of time to move between buildings. You may assume that the time required to place a bomb is negligible. Each commando can carry unlimited number of bombs and there is an unlimited supply of commando troops for the mission.
Input starts with an integer T (≤50), denoting the number of test cases.
The first line of each case starts with a positive integer N (1 ≤ N ≤ 100), where N denotes the number of buildings in the head quarter. The next line contains a positive integer R, where Ris the number of roads connecting two buildings. Each of the next R lines contain two distinct numbers u v (0 ≤ u, v < N), this means there is a road connecting building u to building v. The buildings are numbered from 0 to N-1. The last line of each case contains two integers s d (0 ≤ s, d < N). Where s denotes the building from where the mission starts and d denotes the building where they must meet. You may assume that two buildings will be directly connected by at most one road. The input will be given such that, it will be possible to go from any building to another by using one or more roads.
Output
For each case, print the case number and the minimum time required to complete the mission.
Sample Input |
Output for Sample Input |
| 2430 1
2 1 1 3 0 3 2 1 0 1 1 0 |
Case 1: 4Case 2: 1 |
题目类型：最短路
算法分析：使用SPFA和一个邻接表、一个逆邻接表分别求得最短路径，然后将每个点的两个最短路相加再取最大值，否则会WA！！！！！！
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define i64 long long const int INF = 0x7FFFFFFF; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 300 + 66; //分别表示顶点v。w和下一个邻接的位置 struct Node { int v, w, next; }; Node edge[maxn*maxn]; int head[maxn], edgelen;//分别表示顶点的表头节点和边的数量 Node redge[maxn*maxn]; int rhead[maxn], redgelen; //将所有的数组均初始化为-1 void Init () { memset (head, -1, sizeof (head)); memset (edge, -1, sizeof (edge)); edgelen = 0; memset (rhead, -1, sizeof (rhead)); memset (redge, -1, sizeof (redge)); redgelen = 0; } //使用头插法构建 void AddEdge (int u, int v, int w) { edge[edgelen].v = v; edge[edgelen].w = w; edge[edgelen].next = head[u]; head[u] = edgelen++; redge[redgelen].v = u; redge[redgelen].w = w; redge[redgelen].next = rhead[v]; rhead[v] = redgelen++; } //分别表示源点到其他顶点的最短距离、顶点是否在队列中的判断数组、顶点入队列的次数和顶点个数 long long dis[maxn], inq[maxn]; int n, m; long long rdis[maxn], rinq[maxn]; //数组下标从1开始 void spfa (int s) { for (int i = 1; i <= n; i++)//初始化dis数组和inq数组 { dis[i] = INF; inq[i] = 0; } dis[s] = 0;//将源点的dis数组值初始化为0，重要！！ queue <int> qu; qu.push (s); inq[s]++;//将源点标志为在队列中 while (!qu.empty ()) { int tt = qu.front(); qu.pop (); inq[tt]--; int pa = head[tt]; while (pa != -1) { int pb = edge[pa].v; if (dis[tt] < INF && dis[pb] > dis[tt] + edge[pa].w)//松弛操作 { dis[pb] = dis[tt] + edge[pa].w; if (!inq[pb])//如果被松弛的节点不在队列中，则将该节入队 { qu.push (pb); inq[pb]++; } } pa = edge[pa].next; } } } //数组下标从1开始 void rspfa (int s) { for (int i = 1; i <= n; i++)//初始化dis数组和inq数组 { rdis[i] = INF; rinq[i] = 0; } rdis[s] = 0;//将源点的dis数组值初始化为0，重要！！ queue <int> qu; qu.push (s); rinq[s]++;//将源点标志为在队列中 while (!qu.empty ()) { int tt = qu.front(); qu.pop (); rinq[tt]--; int pa = rhead[tt]; while (pa != -1) { int pb = redge[pa].v; if (rdis[tt] < INF && rdis[pb] > rdis[tt] + redge[pa].w)//松弛操作 { rdis[pb] = rdis[tt] + redge[pa].w; if (!rinq[pb])//如果被松弛的节点不在队列中，则将该节入队 { qu.push (pb); rinq[pb]++; } } pa = redge[pa].next; } } } int main() { // CPPFF; int t, flag = 1; cin >> t; while (t--) { Init (); cin >> n >> m; for (int i = 1; i <= m; i++) { int u, v; cin >> u >> v; u++, v++; AddEdge(u, v, 1); AddEdge(v, u, 1); } int s, e; cin >> s >> e; spfa (s + 1); rspfa (e + 1); long long maxval = -INF; for (int i = 1; i <= n; i++) maxval = max (maxval, dis[i] + rdis[i]); cout << "Case " << flag++ <<": " << maxval << endl; } return 0; } |
- « 上一篇：lightoj1164
- lightoj1183：下一篇 »