思路:
- 翻译题…翻译题…
难道是我校被Q了吗?- 正权无向稠密图,求源点到所有点的最短路,输出最长一条的长度。
- 使用:Dijkstra,邻接矩阵,atoi函数。
代码:
//0ms 748kB
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 105;
int N;
int mp[maxn][maxn];
int dis[maxn];
struct NODE{
int id;
int dis;
friend bool operator > (NODE a , NODE b){
return a.dis > b.dis;
}
NODE(int id,int dis) : id(id) , dis(dis) {} ;
};
priority_queue<NODE , vector<NODE> , greater<NODE> > Q;
bool vis[maxn];
int ans = 0;
void IJK(){
memset(vis,0,sizeof(vis));
memset(dis,INF,sizeof(dis));
Q.push(NODE(1,0));dis[1]=0;
while(Q.size()){
NODE cur = Q.top() ; Q.pop() ;
if(vis[cur.id])
continue;
vis[cur.id] = true;
for(int i=1;i<=N;i++){
if(vis[i])
continue;
if(dis[i] > dis[cur.id] + mp[cur.id][i]){
dis[i] = dis[cur.id] + mp[cur.id][i];
Q.push(NODE(i,dis[i]));
}
}
}
for(int i=1;i<=N;i++)
if(dis[i] == INF)
continue;
else
ans = max(ans , dis[i]);
return ;
}
int main(){
cin>>N;
for(int i=2;i<=N;i++){
for(int j=1;j<=i-1;j++){
char str[30];
scanf("%s",str);
if(str[0] == 'x')
mp[i][j] = mp[j][i] = INF;
else
mp[i][j] = mp[j][i] = atoi(str);
}
}
for(int i=1;i<=N;i++)
mp[i][i] = 0;
IJK();
cout<<ans<<endl;
return 0;
}