运行数据:
0 0 0
0 1 13
0 2 0
0 3 4
0 4 0
1 0 13
1 1 0
1 2 15
1 3 0
1 4 5
2 0 0
2 1 0
2 2 0
2 3 12
2 4 0
3 0 4
3 1 0
3 2 12
3 3 0
3 4 0
4 0 0
4 1 0
4 2 6
4 3 3
4 4 0
#include
using namespace std;
const int n = 5;
const int e = 25;
int sum1[5];
int sum2[5];
int sum3[5];
int j = 0;
int i = 0;
int Min;
int l;
#define max 20
class Graph
{
public:
int arcs[n + 1][n + 1];
int a[n + 1][n + 1];
int path[n + 1][n + 1];
void floyd(Graph& t, const int n);
};
void Graph::floyd(Graph& t, const int n)
{
int i, j, w;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
{
if (i == j)
t.arcs[i][j] = 0;
else
t.arcs[i][j] = max;
for (int k = 0; k < e; k++)
{
cin >> i >> j >> w;
t.arcs[i][j] = w;
}
cout << endl;
}
for(int i=0;i0; j < n; j++)
{
t.a[i][j] = t.arcs[i][j];
if((i != j) && (t.a[i][j] < max))
t.path[i][j] = i;
else
t.path[i][j] = 0;
}
for (int k = 0; k < n; k++)
{
for(i=0;i0;j1、输出邻接矩阵
for (i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cout << t.arcs[i][j] << " ";
}
cout << endl;
}
cout << endl;
//2、输出邻接表
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
if (i != j)
{
int next = t.path[i][j];
cout << j;
cout << "<--" << i << " " << t.a[i][j] << " ";
}
}
cout << endl;
}
cout << endl;
//3、输出最短路径的邻接矩阵
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
cout << t.a[i][j] << " ";
}
cout << endl;
}
cout << endl;
//4、输出点到所有点的路程的和
for (i = 0; i < n; i++)
{
sum1[i] = 0;
for (int j= 0; j< n; j++)
{
if (i != j)
{
cout << t.a[i][j] << ":";
int next = t.path[i][j];
cout << j;
while (next != i)
{
cout << "<--" << next;
next = t.path[i][next];
}
cout << "<--" << i << endl;
sum1[i] += t.a[i][j];
}
}
cout << " 点" << i << " 到所有点的路程和为: " << sum1[i] << endl;
}
//5、逆输出所有点到点路径的和
for (i = 0; i < n; i++)
{
sum2[i] = 0;
for (j = 0; j < n; j++)
{
if (i != j)
{
cout << t.a[j][i] << ":";
int next = t.path[j][i];
cout << i;
while (next != j)
{
cout << "<--" << next;
next = t.path[j][next];
}
cout << "<--" << j << endl;
}
sum2[i] += t.a[j][i];
}
cout << " 所有的点到" << i << " 路程和为: " << sum2[i] << endl;
}
//6、输出所有点往返路程的和
for (int o = 0; o < n; o++)
{
sum3[o] = sum1[o] + sum2[o];
cout << " 点" << o << " 的往返路程的和为: " << sum3[o] << endl;
}
Min = sum3[0];
//7、输出最短路程和医院建址
for (int h = 0; h < n; h++)
{
if (sum3[h] <= Min)
{
Min = sum3[h];
l = h;
}
}
cout << " 比较可得在点" << l << " 那里建立医院" << Min << " 为最短路程" << endl;
}
int main()
{
Graph t;
t.floyd(t, n);
return 0;
}