#include <iostream.h>
#include <fstream.h>
#define M 99999
int 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;
}

测试数据：
11
2 2 2 4 8
2 5 1 4 6
2 7 9 1 1
1 3 7
2 9 1 4 5
3 5 3 4 1 7 4
3 4 7 9 3 10 1
2 5 2 11 9
2 6 6 8 7
2 9 1 11 4
1 9 2

11表示有11个顶点的图
2 2 2 4 8
2表示第一个顶点射出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

评论