1 //Accepted    320 KB    16 ms  2 //有n个顶点,边权用A表示  3 //给出下三角矩阵，求从一号顶点出发到各点的最短路的最大值  4 #include <cstdio>  5 #include <cstring>  6 #include <iostream>  7 #include <queue>  8 #include <cmath>  9 #include <algorithm> 10 using namespace std; 11 /** 12   * This is a documentation comment block 13   * 如果有一天你坚持不下去了，就想想你为什么走到这儿！ 14   * @authr songt 15   */ 16 const int imax_n = 105; 17 const int imax_e = imax_n*imax_n; 18 const int inf = 100000000; 19 struct node 20 { 21     int u,v,c; 22     node(int u=0,int v=0,int c=0):u(u),v(v),c(c) 23     { 24  25     } 26 }p[imax_e]; 27 int head[imax_n]; 28 int next[imax_e]; 29 bool vis[imax_n]; 30 int dis[imax_n]; 31 int cnt[imax_n]; 32 int n; 33 int e=0; 34 void init() 35 { 36     memset(head,-1,sizeof(head)); 37     memset(next,-1,sizeof(next)); 38     e=0; 39 } 40 void addEdge(int u,int v,int c) 41 { 42     p[e]=node(u,v,c); 43     next[e]=head[u]; 44     head[u]=e++; 45 } 46 bool relax(int u,int v,int c) 47 { 48     if (dis[v]>dis[u]+c) 49     { 50         dis[v]=dis[u]+c; 51         return true; 52     } 53     return false; 54 } 55 queue<int > q; 56 bool spfa(int src) 57 { 58     while (!q.empty()) q.pop(); 59     memset(vis,0,sizeof(vis)); 60     memset(cnt,0,sizeof(cnt)); 61     for (int i=1;i<=n;i++) 62     dis[i]=inf; 63     dis[src]=0; 64     q.push(src); 65     vis[src]=1; 66     cnt[src]++; 67     while (!q.empty()) 68     { 69         int pre=q.front(); 70         q.pop(); 71         vis[pre]=0; 72         for (int i=head[pre];i+1;i=next[i]) 73         { 74             if (relax(pre,p[i].v,p[i].c) && !vis[p[i].v]) 75             { 76                 if ((++cnt[p[i].v])>=n) return false; 77                 vis[p[i].v]=1; 78                 q.push(p[i].v); 79             } 80         } 81     } 82     return true; 83 } 84 char s[10]; 85 int main() 86 { 87     while (scanf("%d",&n)!=EOF) 88     { 89         init(); 90         for (int i=2;i<=n;i++) 91         { 92             for (int j=1;j<i;j++) 93             { 94                 scanf("%s",s); 95                 if (s[0]==‘x‘) continue; 96                 int c=atoi(s); 97                 //printf("c=%d\n",c); 98                 addEdge(i,j,c); 99                 addEdge(j,i,c);100             }101         }102         spfa(1);103         int ans=0;104         for (int i=1;i<=n;i++)105         if (dis[i]>ans) ans=dis[i];106         printf("%d\n",ans);107     }108     return 0;109 }