555. 网络探测

★☆   输入文件：ping.in   输出文件：ping.out   简单对比

时间限制：1 s   内存限制：128 MB

【问题描述】

   当出现网络故障时，我们经常使用“ping”命令来检测电脑是否能与其它电脑连通。

   举例说明，如果想知道我们的电脑是否能连上中山大学的主机，可以使用命令“ping www.zsu.edu.cn”，如果网络通畅，那么我们将会收到下面这样的反馈信息：

   Reply from 202.116.64.9:bytes=32 time=1ms TTl=126

   Reply from 202.116.64.9:bytes=32 time< 1ms TTl=126

   可是，我们究竟是如何获取以上信息的呢？特别是用了多长时间？下面就说说“Ping”的原理，请注意，本原理只跟本题有关，而真实的“ping”命令处理过程会有所不同。

   首先，跟“Ping”的过程相关的有两种信息，即请求和回应。

   请求信息包含一个时间流逝段，用来记录请求信息发出后经过了多长时间，我们假定，在网络中每一个主机（包括路由、交换机、电脑等）都是非常“有涵养”的，如果它们不是所接收到信息的目标机的话，它们就会更新信息中的时间流逝段，增加从信息转发的主机到达该机的时间，并且把这个信息发送给所有跟它连通的主机。因此，当我们发出请求信息包之后，网络可以貌似自动地把它传输至目标主机。

   一旦目标主机接收到一条请求信息，它就会回复一条回应信息。回应信息也包含一个时间流逝段，这个时间流逝段是直接从所收到的请求信息中的时间流逝段复制而来的，而且在以后的中转传输中将不再被改变，就这样，网络又貌似自动地回复了我们。这就是为什么我们可以知道网络通畅与否，同时可以得知从我们的电脑上传输一条信息到目标机所需的最短时间了。

   准确地说，在上面“Ping”的处理过程中还存在一个问题，假定某两台中转电脑A和B是直接连通的，一条目标机为电脑C的信息到达了A，那么A将把这条信息传输给B，而B也将会把这条信息再传回给A，（因为它们都是有“涵养”的嘛！），那么这条信息将在A与B之间无限重复的发送下去，为了解决这个问题，如果一条信息已经被转发了超过10次（每次从主机A发送一条信息至主机B称为一次转发），那么接收到这条信息的主机将丢弃该信息。

   你的任务是：给定网络的详情，怎样确定回应的时间。请注意，这里所说的回应时间是指从源主机传输一条信息至目标主机所用的最短时间。 

 

【输入格式】

   输入文件第一行有3个整数，n(n≤1000)、m和t(0≤t≤n)，其中n表示网络中主机的个数（包括我们自己的电脑），m表示网络中直接连通的主机对数， t表示我们想要ping的目标主机。（可以设定我们的电脑为主机0）

   接下来有m行，每一行有3个整数，a(0≤a< n)、b(0≤b< n)和c(0< c≤1000)，表示主机a与主机b直接连通，而信息从a传至b以及从b传至a的时间均为c。  

【输出格式】

   对于输入的数据，如果我们的电脑能得到目标主机的回应，请输出回应时间，否则输出“no”。

【输入样例】

输入文件名：ping.in

3 2 2

0 1 2

1 2 3

输出文件名：ping.out

5

 

 

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define N 100101#define maxn 0x7fffffffusing namespace std;queue
            
             q;bool vis[N];int n,m,s,e,x,y,z,tot,f[N],dis[N],head[N];struct Edge{ int to,dis,from,next;}edge[N<<1];int add(int x,int y,int z){ tot++; edge[tot].to=y; edge[tot].dis=z; edge[tot].next=head[x]; head[x]=tot;}int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} return x*f;}int spfa(int s){ for(int i=0;i
             
              =10) break;vis[x]=false; for(int i=head[x];i;i=edge[i].next) { int t=edge[i].to; if(dis[t]>dis[x]+edge[i].dis) { f[t]=f[x]+1; dis[t]=dis[x]+edge[i].dis; if(vis[t]) continue; q.push(t);vis[t]=true; } } }}int main(){ freopen("ping.in","r",stdin); freopen("ping.out","w",stdout); n=read(),m=read(),e=read(); for(int i=1;i<=m;i++) { x=read(),y=read(),z=read(); add(x,y,z),add(y,x,z); } spfa(0); if(dis[e]==maxn) printf("no"); else printf("%d",dis[e]); return 0;}