题目:
在网络中，发送一个包需要知道对方的物理地址，当不知道物理地趣的时候，就要向网络中广播发送对方的IP地址，然后每一台计算会收到这个广播，如果IP和自己的计算对上，就把自己的物理地址发送出去。
现在有n台计算，编号从1到n，现在1号计算向网络中发送广播，问经过多少时间后所有的计算机都会收到这个广播。
输入的网络保证所有的计算机之间是可以相互通信的。
输入
单组测试数据。
第一行有一个整数n(1 <= n <= 100)。
接下来输入一个邻接矩阵A，A的大小是n x n。里面的元素要么是一个非负整数，或者是一个字符x。如果A[i][j]是x那么第i台计算机和第j台计算机没有直接相连。否则表示信号在第i台计算机和第j台计算机之间传播需要A[i][j]的时间。
自己发给自己是不需要时间的所以对于所有的 1 <= i <= n，A[i][i] = 0。输入的网络是一个无向图，所以A[i][j] = A[j][i]。那么只需要输入矩阵的下三角部分即可。
那么接下来给出n-1行，
第一行有一个整数表示A[2][1]。
第二行有两个整数表示A[3][1]和A[3][2]。
。。。
第n-1行有n-1个整数A[n][1],A[n][2], A[n][3]… A[n][n-1]。
0<=A[i][j]<=100。
输出
输出一个整数表示答案。
输入样例
样例输入1
5
50
30 5
100 20 50
10 x x 10
输出样例
样例输出1
35
解法：最短路裸题
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| #include<stdio.h>
#include<iostream>
#include<algorithm>
#include <cstdlib>
#include<string>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;
struct Node
{
int to;
long long len;
bool operator<(const Node &a) const
{
return len > a.len;
}
};
bool isUsed[510];
long long ans[510];
vector<Node> NodeQueue[510];
void addEdge(int s, int e, int len)
{
NodeQueue[s].push_back((Node){e,len});
NodeQueue[e].push_back((Node){s,len});
}
int n;
priority_queue<Node> PriNodeQueue;
int main()
{
scanf("%d", &n);
for(int i = 2; i <= n; i++)
for(int j = 1; j < i; j++){
string s;
cin >> s;
if(s != "x"){
int len = atoi(s.c_str());
//printf("%d\n", len);
addEdge(i,j,len);
}
}
for(int i = 0; i < 505; i++)
ans[i] = 999999999999;
ans[1] = 0;
PriNodeQueue.push((Node){1,0});
while(!PriNodeQueue.empty()){
Node now = PriNodeQueue.top();
PriNodeQueue.pop();
int u = now.to;
if(!isUsed[u]){
isUsed[u] = true;
for(int i = 0; i < NodeQueue[u].size(); i++){
if(!isUsed[NodeQueue[u][i].to]){
int v = NodeQueue[u][i].to;
int len = NodeQueue[u][i].len;
if(ans[v] > ans[u] + len)
{
ans[v] = ans[u] + len;
PriNodeQueue.push((Node){v,ans[v]});
}
}
}
}
}
long long a = 0;
for(int i = 1; i <= n; i++){
//printf("%d\n", ans[i]);
a = max(a, ans[i]);
}
printf("%lld", a);
return 0;
}
|