学步园

还是Dijstra，代码如下：

#include<stdio.h>
#define max_edge 510
#define max_int 100000
typedef struct Node_Type{
    int dis;
    int cost;    
}Node;
int n,m,s,d,cnt=0;
int vst[max_edge],pre[max_edge];
int Dis[max_edge],Cost[max_edge];
Node map[max_edge][max_edge];
void init(){
     int i,j;
     for(i=0;i<n;i++){
         vst[i]=0;
         Dis[i]=max_int;
         Cost[i]=max_int;
         for(j=0;j<n;j++){
             map[i][j].dis=max_int;
             map[i][j].cost=max_int;
         }                 
     }    
}
void Dijstra(){
    int i,j,k,mindis;
	Dis[s]=0;
	Cost[s]=0;
	pre[s]=s;
	for(i=1;i<=n;i++){
		mindis=max_int;
		for(j=0;j<n;j++){
			if(!vst[j]&&Dis[j]<mindis){
				k=j;
				mindis=Dis[j];
			}
		}
		vst[k]=1;
		if(k==d) return;
		for(j=0;j<n;j++){
			if(!vst[j]){
				if(Dis[j]>Dis[k]+map[k][j].dis){
					Dis[j]=Dis[k]+map[k][j].dis;
					Cost[j]=Cost[k]+map[k][j].cost;
					pre[j]=k;
				}
				else if(Dis[j]==Dis[k]+map[k][j].dis){
					if(Cost[j]>Cost[k]+map[k][j].cost){
						Cost[j]=Cost[k]+map[k][j].cost;
						pre[j]=k;
					}			
				}	
			}				
		}
	}
}
void printPath(int x){
    if(pre[x]==x){
		printf("%d ",x);
	}
	else{
		printPath(pre[x]);
		printf("%d ",x);
	}
}
int main(){
	 int i,j;
	 int c1,c2,di,co; 
	 scanf("%d %d %d %d",&n,&m,&s,&d);
	 init();
	 for(i=0;i<m;i++){
	     scanf("%d %d %d %d",&c1,&c2,&di,&co);
        map[c1][c2].dis=map[c2][c1].dis=di;
        map[c1][c2].cost=map[c2][c1].cost=co;	 
	 }
	 Dijstra();
	 printPath(d);
	 printf("%d %d\n",Dis[d],Cost[d]);
    return 0;
}