题目大意:BIT最近要取会他们的超级计算机,32处理器阿波罗奥德赛与分层通信子系统分布式共享内存的机器(听着很高端大气),瓦伦丁*麦基的顾问杰克*斯威特告诉她基准测试的新系统。(没有明白什么意思)
“因为阿波罗是一个分布的共享内存的机器,内存的访问和交流通信的时间是不统一的”瓦伦丁告诉斯威特。。。。。。(受不了了,这什么破英语,又臭又长还对话!!!!)
直接说这道题的意思算求,就是给一个临街矩阵,这个邻接矩阵因为上三角跟下三角一样,所以只给了下三角,* 号代表两点不相连,然后求出来点1到达所有点的最短时间里面的那个最大的值!!!(直接说多简单啊,还整这么长的的英文,我擦。。。。。)
很明显这是一个裸的最短路dij,spfa随便搞都行
连修改都没有直接就过了...过了....…^^
#include<algorithm>
#include<queue>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;
const int maxn = 105;
const int oo = 0xfffffff;
struct node
{
int y, time;
node(int p, int t):y(p), time(t) {}
};
vector<node> G[maxn];
int v[maxn];
void spfa(int s)
{
queue<int> Q;
Q.push(s);
while(Q.size())
{
s = Q.front();
Q.pop();
int len = G[s].size();
for(int i=0; i<len; i++)
{
node q = G[s][i];
if(v[q.y] > v[s]+q.time)
{
v[q.y] = v[s] + q.time;
Q.push(q.y);
}
}
}
}
int main()
{
int N;
while(scanf("%d", &N) != EOF)
{
int i, j, x;
char s[30];
for(i=1; i<=N; i++)
{
v[i] = oo;
G[i].clear();
}
v[1] = 0;
for(i=2; i<=N; i++)
for(j=1; j<i; j++)
{
scanf("%s", s);
if(s[0] != 'x')
{
sscanf(s, "%d", &x);
G[i].push_back(node(j, x));
G[j].push_back(node(i, x));
}
}
spfa(1);
int ans = -oo;
for(i=1; i<=N; i++)
ans = max(ans, v[i]);
printf("%d\n", ans);
}
return 0;
}