UVa 336 A Node Too Far

题目描述为了避免网络消息数据包在网络中无限循环的问题每个消息都包含一个生存时间Time To Live, TTL\texttt{Time To Live, TTL}Time To Live, TTL字段。该字段包含消息在被丢弃之前可以转发的节点数站点、计算机等。每次一个站点接收到消息时它将TTL\texttt{TTL}TTL字段减111。如果消息的目的地就是当前站点则忽略TTL\texttt{TTL}TTL字段的值。但如果消息必须转发且减111后的TTL\texttt{TTL}TTL字段为000则消息不会被转发。在本题中给定多个网络的描述对于每个网络需要确定给定初始节点和TTL\texttt{TTL}TTL值时无法到达的节点数量。输入格式输入包含多个网络配置。每个网络描述以整数NCNCNC开头表示节点之间的连接数。NC0NC 0NC0表示输入数据结束。接下来NCNCNC行每行包含两个正整数表示连接两个节点的通信线路。任意一对节点之间最多有一条直接通信线路每个网络的节点数不超过303030。每个网络配置之后有多个查询查询格式为两个整数起始节点编号和初始TTL\texttt{TTL}TTL设置。查询以一对0 0结束。输出格式对于每个查询输出一行显示测试用例编号从111开始、不可达节点数、起始节点和初始TTL\texttt{TTL}TTL值。样例输入16 10 15 15 20 15 55 10 50 55 40 55 60 40 20 40 50 50 60 60 65 20 25 20 30 30 47 35 30 35 40 35 50 35 2 35 3 1 1 1 2 3 2 3 3 0 0 0样例输出Case 1: 5 nodes not reachable from node 35 with TTL 2. Case 2: 1 nodes not reachable from node 35 with TTL 3. Case 3: 8 nodes not reachable from node 1 with TTL 1. Case 4: 5 nodes not reachable from node 1 with TTL 2. Case 5: 3 nodes not reachable from node 3 with TTL 2. Case 6: 1 nodes not reachable from node 3 with TTL 3.题目分析问题的本质这是一个图中受限距离可达性问题。给定一个无向图从起始节点sss出发消息每经过一条边TTL\texttt{TTL}TTL减111。消息可以到达的节点是那些从sss出发的最短路径长度≤TTL\leq \texttt{TTL}≤TTL的节点。不可达节点包括最短路径长度TTL \texttt{TTL}TTL的节点图本身不可达的节点但题目保证图连通不保证需考虑实际上由于每条边消耗111个TTL\texttt{TTL}TTL消息能到达的节点正是那些与sss的距离最短路径长度≤TTL\leq \texttt{TTL}≤TTL的节点。因此问题转化为计算所有节点之间的最短路径对于每个查询(s,TTL)(s, \texttt{TTL})(s,TTL)统计所有距离TTL \texttt{TTL}TTL的节点数量节点编号处理节点编号是正整数但可能不连续如样例中的10,15,20,25,30,35,40,47,50,55,60,6510,15,20,25,30,35,40,47,50,55,60,6510,15,20,25,30,35,40,47,50,55,60,65。需要进行坐标离散化将节点编号映射到连续的1∼N1 \sim N1∼N索引以便使用邻接矩阵。图的大小每个网络节点数≤30\leq 30≤30使用Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall算法计算全源最短路径非常合适。参考代码// A Node Too Far// UVa ID: 336// Verdict: Accepted// Submission Date: 2016-06-26// UVa Run Time: 0.040s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){ios::sync_with_stdio(false);intdistances[40][40];// 距离矩阵最大 30 个节点多预留一些空间mapint,intindexer;// 节点编号 → 索引映射intcases0;intn;while(cinn,n){// 初始化距离矩阵为无穷大for(inti0;i40;i)for(intj0;j40;j)distances[i][j]100000;indexer.clear();// 读取边并离散化节点编号for(inti1;in;i){intstart,end;cinstartend;// 为未出现过的节点分配新索引if(indexer.find(start)indexer.end())indexer[start]indexer.size()1;if(indexer.find(end)indexer.end())indexer[end]indexer.size()1;intsindexer[start];inteindexer[end];distances[s][e]1;distances[e][s]1;}intNindexer.size();// 实际节点数// 对角线距离为 0for(inti1;iN;i)distances[i][i]0;// Floyd-Warshall 算法计算全源最短路径for(intk1;kN;k)for(inti1;iN;i)for(intj1;jN;j)if(distances[i][k]distances[k][j]distances[i][j])distances[i][j]distances[i][k]distances[k][j];// 处理查询intnode,ttl;while(cinnodettl,node||ttl){// 如果起始节点不在图中则所有节点都不可达// 但题目保证起始节点一定存在于网络中intsindexer[node];intcounter0;for(inti1;iN;i)if(distances[s][i]ttl)counter;coutCase cases: ;coutcounter nodes not reachable from node ;coutnode with TTL ttl.endl;}}return0;}