51nod-1593-物理地址查询

题目: 在网络中，发送一个包需要知道对方的物理地址，当不知道物理地趣的时候，就要向网络中广播发送对方的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 解法：最短路裸题 代码：

#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;
    
}