PAT1030-Travel Plan

		C语言源码：
[cpp]  
#include<stdio.h>  
#include<limits.h>  
typedef struct node  
{  
    int length,cost;  
}node;  
node A[600][600];  
int visited[600];  
node T[600];  
int Stack[600][600];  
int top[600];  
int main()  
{  
    int n,m,i,j,s,t,a,b,length,cost,minlength,mincost,fmin,k;  
    scanf("%d %d %d %d",&n,&m,&s,&t);  
    for(i=0;i<n;i++)  
    {  
        for(j=0;j<n;j++)  
            A[i][j].length=INT_MAX;  
        visited[i]=0;  
        T[i].length=INT_MAX;  
        T[i].cost=INT_MAX;  
        top[i]=0;  
    }  
    for(i=0;i<m;i++)  
    {  
        scanf("%d %d %d %d",&a,&b,&length,&cost);  
        if(length<A[a][b].length||(length==A[a][b].length&&cost<A[a][b].cost))  
        {  
            A[a][b].length=length;  
            A[a][b].cost=cost;  
        }  
        A[b][a].length=A[a][b].length;  
        A[b][a].cost=A[a][b].cost;  
    }  
    visited[s]=1;  
    T[s].length=0;  
    T[s].cost=0;  
    i=s;  
    top[s]=1;  
    Stack[s][0]=s;  
    while(i!=t)  
    {  
        for(j=0;j<n;j++)  
        {  
            if(visited[j]==0)  
            {  
                if(A[i][j].length!=INT_MAX)  
                {  
                    if(T[i].length+A[i][j].length<T[j].length||(T[i].length+A[i][j].length==T[j].length&&T[i].cost+A[i][j].cost<T[j].cost))  
                    {  
                        T[j].length=T[i].length+A[i][j].length;  
                        T[j].cost=T[i].cost+A[i][j].cost;  
                        top[j]=top[i];  
                        for(k=0;k<top[i];k++)  
                            Stack[j][k]=Stack[i][k];  
                    }  
                }  
            }  
        }  
        minlength=INT_MAX;  
        mincost=INT_MAX;  
        for(j=0;j<n;j++)  
        {  
            if(visited[j]==0&&(T[j].length<minlength||(T[j].length==minlength&&T[j].cost<mincost)))  
            {  
                fmin=j;  
                minlength=T[j].length;  
                mincost=T[j].cost;  
            }  
        }  
        visited[fmin]=1;  
        Stack[fmin][top[fmin]++]=fmin;  
        i=fmin;  
    }  
    for(i=0;i<top[t];i++)  
        printf("%d ",Stack[t][i]);  
    printf("%d %d\n",T[t].length,T[t].cost);  
    return 0;  
}  
 
						
		
	

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

上一个：uva639(放车问题）-回溯法
下一个：项目3-程序的多文件组织