九度教程第77题

C语言源码：
[cpp]  
#include<stdio.h>  
#include<limits.h>  
#define maxsize 1010  
int E[maxsize][maxsize][2];//0放长度，1放花费  
int T[maxsize];  
int L[maxsize][2];  
int main()  
{  
    int n,m,a,b,d,p,i,j,s,t,k,min,fmin;  
    scanf("%d %d",&n,&m);//n是顶点数，m是边数  
    while(n||m)  
    {  
        for(i=0;i<n;i++)  
        {  
            for(j=0;j<n;j++)  
            {  
                E[i][j][0]=INT_MAX;  
                E[i][j][1]=INT_MAX;  
            }  
        }  
        for(i=0;i<m;i++)  
        {  
            scanf("%d %d %d %d",&a,&b,&d,&p);  
            E[a-1][b-1][0]=d;  
            E[a-1][b-1][1]=p;  
            E[b-1][a-1][0]=d;  
            E[b-1][a-1][1]=p;  
        }  
        scanf("%d %d",&s,&t);  
        s--;  
        t--;  
        for(i=0;i<n;i++)  
        {  
            T[i]=0;  
            L[i][0]=INT_MAX;  
            L[i][1]=INT_MAX;  
        }  
        L[s][0]=0;  
        L[s][1]=0;  
        T[s]=1;  
        k=s;  
        while(k!=t)  
        {  
            for(i=0;i<n;i++)  
            {  
                if(T[i]==0&&E[k][i][0]!=INT_MAX)  
                {  
                    if(L[k][0]+E[k][i][0]<L[i][0])  
                    {  
                        L[i][0]=L[k][0]+E[k][i][0];  
                        L[i][1]=L[k][1]+E[k][i][1];  
                    }  
                    else  
                        if((L[k][0]+E[k][i][0]==L[i][0])&&(L[k][1]+E[k][i][1]<L[i][1]))  
                            L[i][1]=L[k][1]+E[k][i][1];  
                }  
            }  
            fmin=-1;  
            min=INT_MAX;  
            for(i=0;i<n;i++)  
            {  
                if(T[i]==0&&L[i][0]<min)  
                {  
                    min=L[i][0];  
                    fmin=i;  
                }  
            }  
            T[fmin]=1;  
            k=fmin;  
        }  
        printf("%d %d\n",L[t][0],L[t][1]);  
        scanf("%d %d",&n,&m);  
    }  
}  
 

补充：软件开发 , C++ ,

上一个：九度教程第78题
下一个：九度教程第76题