#include <iostream.h>#include <fstream.h>#define M 99999int main(){ int G[100][100]; int n; int p[100],flag[100],s[100]; int cur; int m,k,l,i,j; ifstream fin("in.txt"); //enter fin>>n; for(i=0;i<n;i++)  for(j=0;j<n;j++)   G[i][j]=M; for(i=0;i<n;i++) {  fin>>m;  for(j=0;j<m;j++)  {   fin>>k>>l;   G[i][k-1]=l;  } } for(i=0;i<n;i++) {  flag[i]=0;  s[i]=M; } cur=0; flag[cur]=1; s[cur]=0; p[cur]=0; for(i=1;i<n;i++) {  for(j=0;j<n;j++)  {   if(flag[j]==0)   {    m=s[cur]+G[cur][j];    if(m<s[j])    {     s[j]=m;     p[j]=cur;    }   }  }  m=M;  for(j=0;j<n;j++)  {   if(flag[j]==0)   {    if(s[j]<m)    {     m=s[j];     cur=j;    }   }  }  flag[cur]=1;  if(s[cur]==M)  {   //continue;   p[cur]=0;   for(j=0;j<n;j++)    if(flag[j]==0)    {     s[j]=M;     p[j]=0;     flag[j]=1;    }   break;  } }  ofstream fout("out.txt"); for(i=1;i<n;i++) {  if(s[i]==M)  {  cout<<"从第1个点到第"<<i+1<<"的最短路为:M.\n";  fout<<"从第1个点到第"<<i+1<<"的最短路为:M.\n";  }  else  {  cout<<"从第1个点到第"<<i+1<<"的最短路为:"<<s[i]<<".\n";  cout<<"路径为:"<<i+1;  fout<<"从第1个点到第"<<i+1<<"的最短路为:"<<s[i]<<".\n";  fout<<"路径为:"<<i+1;   k=p[i];   cout<<" <-"<<k+1;   fout<<" <-"<<k+1;  while(k!=0)  {   k=p[k];   cout<<" <-"<<k+1;   fout<<" <-"<<k+1;  }  }  cout<<endl<<endl;  fout<<endl<<endl; } return 0;} 测试数据：112 2 2 4 82 5 1 4 62 7 9 1 11 3 72 9 1 4 53 5 3 4 1 7 43 4 7 9 3 10 12 5 2 11 92 6 6 8 72 9 1 11 41 9 2 11表示有11个顶点的图2 2 2 4 82表示第一个顶点射出2条线，2 2表示1->2的长度为2。。。。。。。。 输出数据:从第1个点到第2的最短路为:2.路径为:2 <-1 从第1个点到第3的最短路为:15.路径为:3 <-4 <-1 从第1个点到第4的最短路为:8.路径为:4 <-1 从第1个点到第5的最短路为:3.路径为:5 <-2 <-1 从第1个点到第6的最短路为:10.路径为:6 <-9 <-5 <-2 <-1 从第1个点到第7的最短路为:14.路径为:7 <-6 <-9 <-5 <-2 <-1 从第1个点到第8的最短路为:11.路径为:8 <-9 <-5 <-2 <-1 从第1个点到第9的最短路为:4.路径为:9 <-5 <-2 <-1 从第1个点到第10的最短路为:15.路径为:10 <-7 <-6 <-9 <-5 <-2 <-1 从第1个点到第11的最短路为:19.路径为:11 <-10 <-7 <-6 <-9 <-5 <-2 <-1  

评论