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 阅读(640) 评论(0)  编辑 收藏 引用 所属分类: ACM 、Algorithm 、课内作业


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理