UVa 336 - A Node Too Far-白红宇

UVa 336 - A Node Too Far

阅读量：6094 次

发布时间：2019-06-20

本文共 1482 字，大约阅读时间需要 4 分钟。

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

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

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
          5 #include 
          
            6 using namespace std; 7 #define NODEN 35 8  9 map
           
             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 LOCAL23 freopen("in", "r", stdin);24 #endif25 int n, kase = 0;26 while (scanf("%d", &n) && n)27 {28 int x, y;29 vertex.clear();30 vector
            
              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
             
               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.\n", ++kase, ans, s, ttl);65 }66 }67 return 0;68 }69

View Code

转载于:https://www.cnblogs.com/xiaobaibuhei/p/3320385.html

你可能感兴趣的文章

eclipse中访问不了tomcat首页server Locations变灰无法编辑