#include<fstream>
#define Maxm 501
using namespace std;
ifstream fin("APSP.in");
ofstream fout("APSP.out");
int p, q, k, m;
int Vertex, Line[Maxm];
int Path[Maxm][Maxm], Map[Maxm][Maxm], Dist[Maxm][Maxm];
void Root(int p,int q)
{
if (Path[p][q]>0)
{
Root(p, Path[p][q]);
Root(Path[p][q], q);
}
else
{
Line[k]=q;
k++;
}
}
int main()
{
memset(Path,0,sizeof(Path));
memset(Map,0,sizeof(Map));
memset(Dist,0,sizeof(Dist));
fin >> Vertex;
for(p=1;p<=Vertex;p++)
for(q=1;q<=Vertex;q++)
{
fin >> Map[p][q];
Dist[p][q]=Map[p][q];
}
for(k=1;k<=Vertex;k++)
{
for(p=1;p<=Vertex;p++)
{
if (Dist[p][k]>0)
{
for(q=1;q<=Vertex;q++)
{
if (Dist[k][q]>0)
{
if (((Dist[p][q]>Dist[p][k]+Dist[k][q])||(Dist[p][q]==0))&&(p!=q))
{
Dist[p][q]=Dist[p][k]+Dist[k][q];
Path[p][q]=k;
}
}
}
}
}
}
for(p=1;p<=Vertex;p++)
{
for(q=p+1;q<=Vertex;q++)
{
fout << "\n==========================\n";
fout << "Source:" << p << '\n' << "Target " << q << '\n';
fout << "Distance:" << Dist[p][q] << '\n';
fout << "Path:" << p;
k=2;
Root(p,q);
for(m=2;m<=k-1;m++)
fout << "-->" << Line[m];
fout << '\n';
fout << "==========================\n";
}
}
fin.close();
fout.close();
return 0;
}
/**//*
注解:無(wú)法連通的兩個(gè)點(diǎn)之間距離為0;
Sample Input
7
00 20 50 30 00 00 00
20 00 25 00 00 70 00
50 25 00 40 25 50 00
30 00 40 00 55 00 00
00 00 25 55 00 10 70
00 70 50 00 10 00 50
00 00 00 00 70 50 00
*/