coreBugZJ

此 blog 已弃。

EOJ 1028 路由器

  1/*
  2EOJ 1028 路由器
  3
  4
  5----问题描述:
  6
  7路由器是网络中用来转发IP报文的一种设备。
  8
  9当路由器收到一个终端或者其它路由器发过来的报文时,它必须选项择最快的一条通信线路通向报文所指向的目标机器(目标机器可能是一个终端,也可能是另一个路由器)。众所周知,在两个路由器之间可能有多条通信线路,你的任务就是给出两个路由器之间最短通信时间。
 10每一个路由器都有一个IP来标识它自己,这个标识是唯一的。任意两点之间的通信时间单位是毫秒。每条通信线路都是全双工的(双向的)。 
 11
 12
 13----输入:
 14
 15第一行为两个整数n和m,n表示有多少个路由器,m表示有多少条通信线路。(2<=n<=100,1<=m<=1000)
 16接下去的m行用来描述路由器之间的线路。每行包括三个元素,两个路由器的IP地址和它们之间通信所花费的时间。
 17然后一行是一个整数t,表示有多少个报文。(1<=t<=1000)
 18接下去的t行是报文。每个报文占一行,为了简化问题,我们在每行中给出两个IP地址,分别是目标地址和源地址。你要做的就是求出两者之间的最短时间。 
 19
 20
 21----输出:
 22
 23对于每个报文,输出一行。每行只包含一个整数,表示报文给的两个IP地址之间的最短通信时间。如果不存在这样的通路,或者IP地址并不存在,则输出-1。 
 24
 25
 26----样例输入:
 27
 284 5
 29168.120.1.1 168.120.1.2 15
 30168.120.1.1 168.120.1.4 47
 31168.120.1.1 168.120.1.3 10
 32168.120.1.2 168.120.1.4 15
 33168.120.1.3 168.120.1.4 25
 343
 35168.120.1.1 168.120.1.4
 36168.120.1.3 168.120.1.4
 37168.120.1.3 202.12.12.12
 38
 39
 40----样例输出:
 41
 4230
 4325
 44-1 
 45
 46
 47----分析:
 48
 49
 50*/

 51
 52
 53#include <stdio.h>
 54#include <string.h>
 55
 56#define  N  102
 57#define  OO 1023456789
 58// OO + OO !!!!
 59
 60#define  IPL  20
 61int maxId;
 62char ipStr[N][IPL];
 63
 64int IpToId( const char * ip ){
 65        int i;
 66        for( i=1; i<=maxId; ++i ){
 67                if( strcmp( ip, ipStr[i] ) == 0 ){
 68                        return i;
 69                }

 70        }

 71        return 0;
 72}

 73
 74int main(){
 75        int w[N][N], i, j, k, n, m;
 76        char ip[IPL];
 77        scanf( "%d%d"&n, &m );
 78        maxId = 0;
 79        for( i=1; i<=n; ++i ){
 80                for( j=1; j<=n; ++j ){
 81                        w[i][j] = OO;
 82                }

 83        }

 84
 85        while( m-- ){
 86                scanf( "%s", ip );
 87                if( ( i = IpToId( ip ) ) == 0 ){
 88                        i = ++maxId;
 89                        strcpy( ipStr[maxId], ip );
 90                }

 91                scanf( "%s", ip );
 92                if( ( j = IpToId( ip ) ) == 0 ){
 93                        j = ++maxId;
 94                        strcpy( ipStr[maxId], ip );
 95                }

 96                scanf( "%d"&k );
 97                if( k < w[i][j] )/////////////////////////////
 98                        w[i][j] = w[j][i] = k;
 99                }

100        }

101
102        for( k=1; k<=n; ++k ){
103                for( i=1; i<=n; ++i ){
104                        for( j=1; j<=n; ++j ){
105                                if( (k!=j) && (k!=i) && (i!=j) ){
106                                        if( w[i][j] > w[i][k] + w[k][j] ){
107                                                w[i][j] = w[i][k] + w[k][j];
108                                        }

109                                }

110                        }

111                }

112                w[k][k] = 0;
113        }

114
115        scanf( "%d"&m );
116        while( m-- ){
117                scanf( "%s", ip );
118                i = IpToId( ip );
119                scanf( "%s", ip );
120                j = IpToId( ip );
121                printf( "%d\n", (i==0)||(j==0)||(w[i][j]==OO) ? -1 : w[i][j] );
122        }

123        return 0;
124}

125

posted on 2012-05-14 16:08 coreBugZJ 阅读(467) 评论(0)  编辑 收藏 引用 所属分类: ACMAlgorithm课内作业


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理