给出下三角矩阵 求单源最短路中的最长路
求下最短路就好,考读题。。
//求单源最短路中的最长路
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cmath>
#include <cstdlib>
using namespace std;
typedef pair<int,int> PII;
const int MAXN=107;
const int MAXM=MAXN*MAXN/2;
const int INF=0x3f3f3f3f;
int head[MAXN],to[MAXM<<1],ne[MAXM<<1],n,m,w,ecnt,T;
int dist[MAXN],wt[MAXM<<1];
void init()
{
ecnt=0;
memset(head,0,sizeof(head));
}
void addedge(int a,int b,int c)
{
ne[++ecnt]=head[a];
head[a]=ecnt;
to[ecnt]=b;
wt[ecnt]=c;
}
queue<int> q;
int inq[MAXN],vis[MAXN];
int spfa(int s)
{
while(!q.empty())
q.pop();
for(int i=1;i<=n;i++)
dist[i]=INF,inq[i]=0,vis[i]=0;
dist[s]=0;
inq[s]=1;
q.push(s);
int ta;
while(!q.empty())
{
int fr=q.front();
q.pop();
inq[fr]=0;
for(int i=head[fr];i;i=ne[i])
{
int v=to[i];
ta=dist[fr]+wt[i];
if(dist[v]>ta)
{
dist[v]=ta;
if(inq[v])continue;
if(++vis[v]>=n)//存在负环
return -1;
inq[v]=1;
q.push(v);
}
}
}
return 1;
}
int main()
{
int ta;
char tb[10];
scanf("%d",&n);
init();
for(int i=1;i<=n;i++)
{
for(int j=1;j<i;j++)
{
scanf("%s",tb);
if(tb[0]=='x')
continue;
ta=atoi(tb);
addedge(i,j,ta);
addedge(j,i,ta);
}
}
spfa(1);
int maxl=0;
for(int i=1;i<=n;i++)
maxl=max(maxl,dist[i]);
printf("%d\n",maxl);
return 0;
}