OJ Board

Code: Select all

#include<stdio.h>
#include<stdlib.h>
#define INF 999999

typedef struct Edge{
	int u,v;
	double d,t;
} Edge;

Edge edge[10100];
Edge tedge[220];
int v,E,TE;
double d[105];
int set[105];
int pre[105];
double max[105];

void print_path(int,int);
void make_set(void);
void Set_union(int ,int );
void mst(void);
int comp(const void*,const void*);
double Max(double a,double b){
	return a>b?a:b ;
}

void main(void){
	int i,j,m,n,a,b;
	double p,q;
	
	
	while(scanf("%d %d",&v,&E)==2){
		scanf("%d %d",&m,&n);
		
		j=0;
		for(i=0;i<E;i++){
			scanf("%d %d %lf %lf",&a,&b,&p,&q);

			edge[j].u=edge[j+1].v=a;
			edge[j].v=edge[j+1].u=b;
			edge[j].t=edge[j+1].t=p;
			edge[j].d=edge[j+1].d=q;

			j+=2;
		}

		E=j;
	
		qsort(edge,E,sizeof(Edge),comp);

		mst();

		for(i=1;i<=v;i++){
			d[i]=INF;
			max[i]=-INF;
			pre[i]=m;
		}
		d[m]=0;
		max[m]=0;

		for(i=0;i<v-1;i++){
			for(j=0;j<TE;j++){
				if(d[tedge[j].v]>d[tedge[j].u]+tedge[j].d){
					d[tedge[j].v]=d[tedge[j].u]+tedge[j].d;
					max[tedge[j].v]=Max(max[tedge[j].u],tedge[j].t);
					pre[tedge[j].v]=tedge[j].u;
				}
			}
		}
		
		print_path(m,n);
		putchar('\n');
		printf("%.1lf %.1lf\n",d[n],max[n]);

	}
}

int comp(const void* x,const void* y){
	Edge* a=(Edge*) x;
	Edge* b=(Edge*) y;

	if(a->t > b->t) return 1;
	else if(a->t < b->t) return -1;
	else{
		if(a->d > b->d) return 1;
		else if(a->d , b->d) return -1;
		else return 0;
	}
}

void make_set(void){
	int i;

	for(i=1;i<=v;i++) set[i]=i;
}

void Set_union(int a,int b){
	int i,j=set[b];

	for(i=1;i<=v;i++){
		if(set[i]==j) set[i]=set[a];
	}
}

void mst(void){
	int i,j;

	make_set();
	j=0;

	for(i=0;i<E;i++){
		if(set[edge[i].u]!=set[edge[i].v]){
			tedge[j].u=tedge[j+1].v=edge[i].u;
			tedge[j].v=tedge[j+1].u=edge[i].v;
			tedge[j].t=tedge[j+1].t=edge[i].t;
			tedge[j].d=tedge[j+1].d=edge[i].d;
			Set_union(edge[i].u,edge[i].v);
			j+=2;
		}
	}

	TE=j;
}

void print_path(int i,int j){
	if(i==j) printf("%d",i);
	else print_path(i,pre[j]);
	if(i!=j) printf(" %d",j);
}