coreBugZJ

此 blog 已棄。

EOJ 1028 路由器

/*
2

EOJ 1028 路由器
3

----問題描述：
6

路由器是網絡中用來轉發IP報文的一種設備。
8

當路由器收到一個終端或者其它路由器發過來的報文時，它必須選項擇最快的一條通信線路通向報文所指向的目標機器（目標機器可能是一個終端，也可能是另一個路由器）。眾所周知，在兩個路由器之間可能有多條通信線路，你的任務就是給出兩個路由器之間最短通信時間。
10

每一個路由器都有一個IP來標識它自己，這個標識是唯一的。任意兩點之間的通信時間單位是毫秒。每條通信線路都是全雙工的(雙向的)。
11

----輸入：
14

第一行為兩個整數n和m，n表示有多少個路由器，m表示有多少條通信線路。(2<=n<=100,1<=m<=1000)
16

接下去的m行用來描述路由器之間的線路。每行包括三個元素，兩個路由器的IP地址和它們之間通信所花費的時間。
17

然后一行是一個整數t，表示有多少個報文。(1<=t<=1000)
18

接下去的t行是報文。每個報文占一行，為了簡化問題，我們在每行中給出兩個IP地址，分別是目標地址和源地址。你要做的就是求出兩者之間的最短時間。
19

----輸出：
22

對于每個報文，輸出一行。每行只包含一個整數，表示報文給的兩個IP地址之間的最短通信時間。如果不存在這樣的通路，或者IP地址并不存在，則輸出-1。
24

----樣例輸入：
27

4 5
29

168.120.1.1 168.120.1.2 15
30

168.120.1.1 168.120.1.4 47
31

168.120.1.1 168.120.1.3 10
32

168.120.1.2 168.120.1.4 15
33

168.120.1.3 168.120.1.4 25
34

3
35

168.120.1.1 168.120.1.4
36

168.120.1.3 168.120.1.4
37

168.120.1.3 202.12.12.12
38

----樣例輸出：
41

30
43

25
44

-1
45

----分析：
48

*/
51

#include <stdio.h>
54

#include <string.h>
55

#define N 102
57

#define OO 1023456789
58

// OO + OO !!!!
59

#define IPL 20
61

int maxId;
62

char ipStr[N][IPL];
63

int 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

int 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

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 閱讀(660) 評論(0) 編輯收藏引用所屬分類: ACM 、Algorithm 、課內作業

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: 微軟2014實習生及秋令營技術類職位在線測試 TopCoder SRM 593 DIV2 第三題生成全排列的非回溯方法（TopCoder SRM 591 DIV 2） A* 算法求解八數碼問題，POJ 1077 Eight POJ 1067 取石子游戲 POJ 2068 Nim POJ 2975 Nim POJ 3696 The Luckiest number POJ 3604 Professor Ben EOJ 1117 剩余定理

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

coreBugZJ

My Links

Blog Stats

常用鏈接

留言簿(10)

隨筆分類(458)

隨筆檔案(268)

相冊

ACM

AI

LaTeX

安全

編程語言

好有道理

技術

開源

科學

數學

圖形圖像

文化

問題（練習＆有趣）

資源

最新隨筆

搜索

最新評論

閱讀排行榜

評論排行榜

EOJ 1028 路由器