#include<iostream> #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define MVNum 100 //最大顶点数 #define MaxInt 32767 using namespace std; typedef struct {//图的邻接矩阵存储表示 int vexnum,arcnum; //图的当前顶点数和边数 int vexs[MVNum]; //顶点表 int arcs[MVNum][MVNum]; //邻接矩阵 }AMGraph; int CreateUDN(AMGraph &G,int vexnum,int arcnum) {//采用邻接矩阵表示法，创建无向网G G.vexnum=vexnum; //输入总顶点数 G.arcnum=arcnum; //输入总边数 if(G.vexnum>MVNum) return ERROR; //超出最大顶点数则结束函数 int i,j,a,b,c; for(i=1;i<=G.vexnum;i++) G.vexs[i]=i; for(i=1;i<=G.vexnum;i++) //初始化邻接矩阵，边的权值均置为极大值 for(j=1;j<=G.vexnum;j++) G.arcs[i][j]=MaxInt; for(i=0;i<G.arcnum;i++) //顶点a和顶点b之间有一条长度为c的路 { cin>>a>>b>>c; G.arcs[a][b]=c; G.arcs[b][a]=c; } return OK; } void ShortPathMAX(AMGraph G,int v0) {//用Dijkstra算法求图G中距离顶点v0的最短路径长度最大的一个顶点 /**************begin************/ /**************end************/ } int main() { int n,m; while(cin>>n>>m) { if(n==0&&m==0) break; AMGraph G; CreateUDN(G,n,m); //创建无向网G int v; cin>>v; ShortPathMAX(G,v); //最长的最短路径的求解 } return 0; }补全代码

#include<iostream>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MVNum 100 //最大顶点数
#define MaxInt 32767
using namespace std;

typedef struct {//图的邻接矩阵存储表示
int vexnum,arcnum; //图的当前顶点数和边数
int vexs[MVNum]; //顶点表
int arcs[MVNum][MVNum]; //邻接矩阵
}AMGraph;

int CreateUDN(AMGraph &G,int vexnum,int arcnum) {//采用邻接矩阵表示法，创建无向网G
G.vexnum=vexnum; //输入总顶点数
G.arcnum=arcnum; //输入总边数
if(G.vexnum>MVNum) return ERROR; //超出最大顶点数则结束函数
int i,j,a,b,c;
for(i=1;i<=G.vexnum;i++)
G.vexs[i]=i;
for(i=1;i<=G.vexnum;i++) //初始化邻接矩阵，边的权值均置为极大值
for(j=1;j<=G.vexnum;j++)
G.arcs[i][j]=MaxInt;
for(i=0;i<G.arcnum;i++) //顶点a和顶点b之间有一条长度为c的路
{
cin>>a>>b>>c;
G.arcs[a][b]=c;
G.arcs[b][a]=c;
}
return OK;
}

void ShortPathMAX(AMGraph G,int v0) {//用Dijkstra算法求图G中距离顶点v0的最短路径长度最大的一个顶点
int dist[MVNum]; //存放当前求出的到各点的最短路径长度
int path[MVNum]; //存放当前求出的最短路径
int s[MVNum]={0}; //标记数组，s[i]=1表示已经求出vi到v0的最短路径
int i,j,k,max;
for(i=1;i<=G.vexnum;i++)
{
dist[i]=G.arcs[v0][i];
if(dist[i]<MaxInt) path[i]=v0;
else path[i]=-1;
}
dist[v0]=0;
s[v0]=1; //初始化，v0到v0的最短路径为0，标记v0已经求出最短路径
for(i=1;i<=G.vexnum;i++)
{
max=0;
for(j=1;j<=G.vexnum;j++)
if(!s[j]&&dist[j]>max) //找到当前未标记的距离v0最远的点
max=dist[k=j];
s[k]=1; //标记该点已经求出最短路径
for(j=1;j<=G.vexnum;j++)
if(!s[j]&&G.arcs[k][j]<MaxInt) //如果k到j有边
if(max<G.arcs[k][j]) max=G.arcs[k][j]; //更新max
if(dist[k]+G.arcs[k][j]>dist[j]) //如果通过k点中转比直接到j点路径更短
{
dist[j]=dist[k]+G.arcs[k][j];
path[j]=k;
}
}
max=0;
for(i=1;i<=G.vexnum;i++)
{
if(dist[i]>max) max=dist[i];
}
cout<<max<<endl; //输出最长的最短路径
}

int main() {
int n,m;
while(cin>>n>>m)
{
if(n==0&&m==0) break;
AMGraph G;
CreateUDN(G,n,m); //创建无向网G
int v;
cin>>v;
ShortPathMAX(G,v); //最长的最短路径的求解
}
return 0;
}