UVa 10816 - Travel in Desert

// UVa 10816 - Travel in Desert

#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
using namespace std;

#define MaxN 101

int color[MaxN], cnt[MaxN], first[MaxN], next[MaxN];

struct edge {
	int a, b;
	double t, l;
};

bool by_t(edge a, edge b) {
	return a.t < b.t;
}

void paint(int ca, int cb) {
	int a;
	for (a = first[ca]; next[a] != 0; a = next[a])
		color[a] = cb;
	color[a] = cb;
	next[a] = first[cb];
	first[cb] = first[ca];
	cnt[cb] += cnt[ca];
	cnt[ca] = 0;
}

double lnk[MaxN][MaxN];
int from[MaxN];
int n, m, s, t;

double dijkstra() {
	// init
	double cost[MaxN];
	for (int i = 1; i <= n; i++)
		cost[i] = -1;
	cost[s] = 0;
	bool yet[MaxN];
	memset(yet, true, sizeof(yet));
	// main
	int nxt = s;
	while (nxt != t && nxt != -1) {
		int now = nxt;
		yet[now] = false;
		nxt = -1;
		for (int i = 1; i <= n; i++)
			if (yet[i]) {
				if (lnk[now][i] != -1 && (cost[i] == -1 || cost[i] > cost[now] + lnk[now][i])) {
					cost[i] = cost[now] + lnk[now][i];
					from[i] = now;
				}
				if (cost[i] != -1 && (nxt == -1 || cost[i] < cost[nxt]))
					nxt = i;
			}
	}
	return cost[t];
}

void print(int i) {
	if (i != s) {
		print(from[i]);
		cout << " " << i;
	} else
		cout << i;
}

int main() {
	while (cin >> n >> m) {
		cin >> s >> t;
		edge e[10000];
		for (int j = 0; j < m; j++)
			cin >> e[j].a >> e[j].b >> e[j].t >> e[j].l;
		sort(e, e + m, by_t);
		for (int i = 1; i <= n; i++) {
			color[i] = i;
			cnt[i] = 1;
			first[i] = i;
			next[i] = 0;
		}
		// init cost
		for (int i = 1; i < n; i++)
			for (int j = i; j <= n; j++) {
				lnk[i][j] = -1;
				lnk[j][i] = -1;
			}
		//
		double sol_t = 0;
		int k = 0;
		for (int j = 0; j < m; j++) {
			// update cost
			if (lnk[e[j].a][e[j].b] == -1 || e[j].l < lnk[e[j].a][e[j].b]) {
				lnk[e[j].a][e[j].b] = e[j].l;
				lnk[e[j].b][e[j].a] = e[j].l;
			}
			// update colors
			int ca = color[e[j].a];
			int cb = color[e[j].b];
			if (ca != cb) {
				if (cnt[ca] < cnt[cb])
					paint(ca, cb);
				else
					paint(cb, ca);
			}
			if (color[s] == color[t]) {
				sol_t = e[j].t;
				k = j;
				break;
			}
		}

		for (int j = k + 1; j < m && e[j].t == e[j - 1].t; j++) {
			// update cost
			if (lnk[e[j].a][e[j].b] == -1 || e[j].l < lnk[e[j].a][e[j].b]) {
				lnk[e[j].a][e[j].b] = e[j].l;
				lnk[e[j].b][e[j].a] = e[j].l;
			}
		}
		// min path
		double sol_l = dijkstra();
		// output
		print(t);
		cout << endl;
		printf("%.1f %.1f\n", sol_l, sol_t);
	}

	return 0;
}