Given a lower triangular matrix, ask what is the longest one in the shortest path from the beginning to other points.

Input: Number of N numbers, then corresponding to the weight of the adjacency matrix

Train of Thought: According to the meaning of the question, it is to use dijkstra directly, because it is the shortest path from a single source and has no negative weight. Then the dist is recycled to find the maximum value at one time.

For the storage of graphs, because the number of numbers is relatively small, and it is also a matrix, so the adjacency matrix is written directly.

Complete problem solving:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <cmath> 
#include <algorithm>

using namespace std;
const int maxn = 105;
const int inf = 0x3f3f3f3f;
typedef pair<int,int> pi;
int n;
int g[maxn][maxn];
int dist[maxn];
void init(){
    memset(dist,inf,sizeof(dist));
    memset(g,0,sizeof(g));
}
void dijkstra(int s){
    priority_queue<pi>Q;
    dist[s] = 0;
    Q.push(make_pair(0,s));
    while(!Q.empty()){
        s = Q.top().second;
        Q.pop();//Do it directly with adjacency matrix
        for(int i=0;i<n;i++){
            if(i==s) continue;
            if(dist[i]>dist[s]+g[s][i]) {
                dist[i] = dist[s]+g[s][i];
                Q.push(make_pair(-dist[i],i));//To update 
            }
        }    
    }
} 
int trans(string s){
    int tmp = 0;
    if(s[0]=='x') return inf;
    else{
        for(int i=0;i<s.size();i++){
            tmp += (s[i]-'0')*pow(10,(s.size()-i-1));            
        }
        return tmp;
    }
}
int main(){

    while(cin>>n){
        init();
        //Starting from 0,0 to save maps
        init();
        string s; 
        int i,j; i = j =0;
        for(i=0;i<n;i++){
            for(j=0;j<i;j++){
                cin>>s;
                g[j][i] = g[i][j] = trans(s);
            }
            g[i][j] = 0;
        }
        dijkstra(0);
        int ans = 0;
        for(int i=1;i<n;i++){
            ans = max(dist[i],ans);
        }
        cout<<ans<<endl;
    }
}