谁可以把这道题解下...
科大讯飞杯的题
二、 最短路径（path）：如图1所示的带权有向图，图中各顶点到其余各点的距离存储在二维数组arcs中，如arcs[j]表示Vi顶点到Vj顶点的距离，若两点间无直接路径则值为∞，如图2所示。编程求V0点到其他各点的最短距离及所经过的顶点。
∞ ∞ 10 ∞ 30 100
∞ ∞ 5 ∞ ∞ ∞
∞ ∞ ∞ 50 ∞ ∞
∞ ∞ ∞ ∞ ∞ 10
∞ ∞ ∞ 20 ∞ 60
∞ ∞ ∞ ∞ ∞ ∞
给的答案好像不对，谁可以讲解下。。
#include <iostream>
using namespace std;
const int n = 6;
const int maxint = 10000;
int cost[n][n] = {{maxint,maxint,10,maxint,30,100},
{maxint,maxint,5,maxint,maxint,maxint},
{maxint,maxint,maxint,50,maxint,maxint},
{maxint,maxint,maxint,maxint,maxint,10},
{maxint,maxint,maxint,20,maxint,60},
{maxint,maxint,maxint,maxint,maxint,maxint}}; //代价矩阵
int dist[n]; //dist表示第i个顶点和顶点V0即起点的最短距离
bool s[n]; // s表示第i个顶点是否放入s中
int prev[n]; //表示从源点到顶点i的最短路径上i的前一个顶点
int main()
{
int i,j;
int newdist;
//初始化
dist[0] = 0; s[0] = true; //把V0放入集合S
for ( i=1;i<n;i++) //初始化其它顶点和V0的最短路径为cost[0]
{
dist=cost[0];
s = false;
if(dist == maxint)prev = -1; //和源点V0有连接的顶点的前一个顶点为V0
else prev = 0;
}
for ( i=0;i<n;i++)
{
/*****************在dist中找没有放到S中且值最小的那个路径*************/
int temp = maxint;
int u = 0;
for ( j=0;j<n;j++)
if((!s[j])&&(dist[j]<temp)){
u = j;
temp = dist[j];
}
s = true; //u表示找到的那个点
/************************************************************************/
/*************************重新调整各dist[j]（J不在S中）******************/
for( j=0;j<n;j++)
if((!s[j])&&(cost[j]<maxint)){
newdist = dist+cost[j];
if(newdist<dist[j]){
dist[j] = newdist;
prev[j] = u;
}
}
}
for(i=0;i<n;i++)
cout << dist << endl;
getchar();
getchar();
return 0;
}
