uva 10816 最小生成树 + 最短路

#include<cstdio>
#include<cstring>
#include<vector>
#include<stack> 
#include<algorithm> 
#include<queue> 
using namespace std;
struct nod{
	int u,v;
	double t,w;
}e[1000100];
int pre[110],n,m,s,t,vis[110];
struct node{
	int to;
	double w;
	node(int a=0,double b=0){
		to=a;
		w=b;
	}
};
vector<node>g[110];
double dis[110];
int find(int x){
	return x==pre[x]?x:find(pre[x]);
}
bool cmp(const nod &a,const nod &b){
	return a.t<b.t;
}
double spfa(){
	for(int i=0;i<=n;i++){
		dis[i]=1000000000;
		vis[i]=0;
		pre[i]=0;
	}
	queue<int> q;
	q.push(s);
	vis[s]=1;
	dis[s]=0;
	memset(pre,0,sizeof(pre));
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=0;i<g[u].size();i++){
			int v=g[u][i].to;
			double w=g[u][i].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				pre[v]=u;
				if(!vis[v]){
					q.push(v);
					vis[v]=1;
				}
			}
		}
	}
	return dis[t];
}
void print(int x){
	if(x!=s)
	print(pre[x]);
	if(x==s)
	printf("%d",x);
	else
	printf(" %d",x); 
}
int main(){
	while(scanf("%d%d",&n,&m) == 2){
		scanf("%d%d",&s,&t);
		for(int i=0;i<=n;i++)
		g[i].clear();
		for(int i=0;i<m;i++){
			scanf("%d%d%lf%lf",&e[i].u,&e[i].v,&e[i].t,&e[i].w);
		}
		for(int i=0;i<=n;i++) pre[i]=i;
		double mmax;
		sort(e,e+m,cmp);
		for(int i=0;i<m;i++){
			int t1=find(e[i].u),t2=find(e[i].v);
			if(t1!=t2) pre[t1]=t2;
			if(find(s) == find(t)){
				mmax=e[i].t;
				break;
			}
		}
		for(int i=0;i<m;i++){
			if(e[i].t<=mmax){
				int u=e[i].u,v=e[i].v;
				double w=e[i].w;
				g[u].push_back(node(v,w));
				g[v].push_back(node(u,w));
			}
		}
		double ans=spfa();
		print(t);
		printf("\n%.1f %.1f\n",ans,mmax);
	}
}