The Fourth Dimension Space

枯叶北风寒，忽然年以残，念往昔，语默心酸。二十光阴无一物，韶光贱，寐难安； 不畏形影单，道途阻且慢，哪曲折，如渡飞湍。斩浪劈波酬壮志，同把酒，共言欢！ -如梦令

再看floyd

 

#include<iostream>
#include<cstdio>
using namespace std;

#define numVertices 500
#define MAXNUM 999999999
double weight[numVertices][numVertices];
double a[numVertices][numVertices];
int path[numVertices][numVertices];

void  floyd() 
{ 
    int i,j,k;
    for   (i     =   0;   i   <   numVertices;   i++)  
    { 
        for   (j   =   0;   j   <   numVertices;   j++) 
        { 
            a[i][j]   =   weight[i][j]; 
            if   (i   !=   j   &&   a[i][j]   <   MAXNUM)  
            { 
                path[i][j]   =   i; 
            } 
            else 
            { 
                path[i][j]   =   -1; 
            } 
        } 
    } 

    for   (k   =   0;   k   <   numVertices;   k++)  
    { 
        for   (i   =   0;   i   <   numVertices;   i++) 
        { 
            for   (j   =   0;   j   <   numVertices;   j++)  
            { 
                if   (a[i][k]   +   a[k][j]   <   a[i][j])
                { 
                    a[i][j]   =   a[i][k]   +   a[k][j]; 
                    path[i][j]   =   path[k][j]; 
                } 
            } 
        } 
    } 
}


int p;
int ans[500];
int f;
void getpath(int i,int j)
{
    p=0;
    f=0;
    int k;
    k=path[i][j];
    while(true)
    {
        
        if(k==-1)
        {
            f=1;
            printf("No answer\n");
            return ;
        }
        else if(k==i)
        {
            printf("最短路径长度为: %lf ",a[i][j]);
            printf("路线为：");

            ans[++p]=k;
            for(int ll=p;ll>=1;ll--)
                printf("%d ",ans[ll]+1);
            printf("%d\n",j+1);
            


            return ;
        }
        else
        {
            ans[++p]=k;
            k=path[i][k];
        
        }
    }
}






int main()
{
    int n;
    int i,j,k;
    int a,b;
    scanf("%d",&n);

    for(j=0;j< numVertices ;j++)
        for(k=0;k< numVertices ;k++)
            weight[j][k]=weight[k][j]=MAXNUM;

    for(i=1;i<=n;i++)
    {
        double c;
        cin>>a>>b>>c;
        weight[a-1][b-1]=weight[b-1][a-1]=c;
    }
    floyd();
    int q;
    cin>>q;
    for(j=1;j<=q;j++)
    {
        cin>>a>>b;
        getpath(a-1,b-1);
    }
    
    return 0;
}

posted on 2010-05-30 17:09 abilitytao 阅读(208) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理