朴素Dijstra
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 3010, M = 30010;
int a[N][N],d[N],n,m;
bool v[N];
void dijkstra(){
memset(d,0x3f,sizeof d);
memset(v,0,sizeof v);
d[1] = 0;
for(int i = 1; i < n; i++){
int x = 0;
//找到全局最小的 && 没被之前“找到”过的点
for(int j = 1; j <= n; j++)
if(!v[j] && (x == 0 || d[j] < d[x])) x = j;
v[x] = 1;
//更新其他点
for(int y = 1; y <= n; y++)
d[y] = min(d[y], d[x] + a[x][y]);
}
}
int main(){
cin >> n;
memset(a, 0x3f, sizeof a);
for(int i = 2; i <= n; i++)
for(int j = 1; j < i; j++)
{
string s; cin >> s;
if(s[0] == 'x') continue;
int sv = 0;
for(int i = 0; i < (int)s.size(); i++) sv *= 10, sv += s[i] - '0';
a[i][j] = a[j][i] = sv;
}
dijkstra();
int ans = 0;
for(int i = 2; i <= n; i++) ans = max(ans, d[i]);
cout << ans;
return 0;
}