题意：两点间的最短距离，并输出路径（按字典序排列），如何理解字典序，如：1>4>5>6的值等于1>2>5>6的值而且都为最短路径，

此时必须输出：1>2>5>6

 

解法：floyd

 

ac代码：

#include
      
       using namespace std;const int INT=0x7fffff;const int M=1000+99;int map[M][M];//存地图int d[M];//存每一个点的税金int path[M][M];//记录点i->j经过的点int n;void floyd(){    int i,j,k;    for(i=1;i<=n;i++)        for(j=1;j<=n;j++)            path[i][j]=j;    for(k=1;k<=n;k++)    {        for(i=1;i<=n;i++)        {            for(j=1;j<=n;j++)            {                if(map[i][k]+map[k][j]+d[k]
       
        path[i][k])                            path[i][j]=path[i][k];                    }            }        }    }}int main(){    while(cin>>n,n)    {        memset(map,0,sizeof(map));        memset(d,0,sizeof(d));        int i,j;        int a,b;        for(i=1;i<=n;i++)        {            for(j=1;j<=n;j++)            {                cin>>a;                if(a!=-1)                    map[i][j]=a;                else                    map[i][j]=INT;            }        }        for(i=1;i<=n;i++)            cin>>d[i];        floyd();//调用floyd函数        while(cin>>a>>b,!(a==-1&&b==-1))        {            printf("From %d to %d :\nPath: ",a,b);            if(a==b) //当自己访问自己时经过的点只需输出自己                cout<
        <
         
          ";                while(path[x][y]!=y)//输出经过的每一个点                {                    cout<
          
           <<"-->";                    x=path[x][y];                }                cout<
           <
            
             j的最短路径 cout<