UVa 336

　　题目大意：在计算机网络中，每条信息都有一个TTL值，在信息到达一个节点时，TTL值首先减1，如果TTL为0，则丢弃该信息报文。给一个网络的配置，给定源点和TTL值，判断该网络中有多少节点不可到达。

　　无权图（无向）上的单源最短路问题，可用BFS解决。

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <map>
 5 #include <queue>
 6 using namespace std;
 7 #define NODEN 35
 8 
 9 map<int, int> vertex;
10 
11 void new_vertex(int x)
12 {
13     if (!vertex.count(x))
14     {
15         int t = vertex.size() + 1;
16         vertex[x] = t;
17     }
18 }
19 
20 int main()
21 {
22 #ifdef LOCAL
23     freopen("in", "r", stdin);
24 #endif
25     int n, kase = 0;
26     while (scanf("%d", &n) && n)
27     {
28         int x, y;
29         vertex.clear();
30         vector<int> G[NODEN];
31         for (int i = 0; i < n; i++)
32         {
33             scanf("%d%d", &x, &y);
34             new_vertex(x);
35             new_vertex(y);
36             G[vertex[x]].push_back(vertex[y]);
37             G[vertex[y]].push_back(vertex[x]);
38         }
39         int s, ttl, cnt;
40         int dist[NODEN];
41         while (scanf("%d%d", &s, &ttl) && (s || ttl))
42         {
43             int st = vertex[s];
44             queue<int> q;
45             memset(dist, -1, sizeof(dist));
46             dist[st] = 0;
47             q.push(st);
48             cnt = 1;
49             while (!q.empty())
50             {
51                 int u = q.front();
52                 q.pop();
53                 for (int i = 0; i < G[u].size(); i++)
54                 {
55                     int v = G[u][i];
56                     if (dist[v] != -1)  continue;
57                     dist[v] = dist[u] + 1;
58                     if (dist[v] > ttl)  goto s;
59                     q.push(v);
60                     cnt++;
61                 }
62             }
63 s:            int ans = vertex.size() - cnt;
64             printf("Case %d: %d nodes not reachable from node %d with TTL = %d.
", ++kase, ans, s, ttl);
65         }
66     }
67     return 0;
68 }
69

View Code