1735.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1735 on 2006-07-23 at 15:23:06 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 128;
const int INF = 1 << 25;

int next[MAX][MAX], n;
int best, path[MAX], pn;

void travel(int);

int main()
{
	int m, i, j;

	while(scanf("%d %d", &n, &m) != EOF) {
		for(i = 0; i < n; i++)
			for(j = 0; j < n; j++) next[i][j] = INF;
		for(i = 0; i < m; i++) {
			int a, b, d;
			scanf("%d %d %d", &a, &b, &d); a--; b--;
			next[a][b] = next[b][a] = min(next[a][b], d);
		}
		best = INF;
		for(i = 0; i < n; i++) travel(i);
		if(best == INF) printf("No solution.\n");
		else for(i = 0; i < pn; i++) printf("%d%c", path[i]+1, (i == pn-1) ? '\n' : ' ');
	}
	
	return 0;
}

void travel(int src)
{
	int d[MAX], prev[MAX], i, j, k;
	bool vst[MAX] = { false };
	int stack[MAX];
	for(i = 0; i < n; i++) d[i] = INF;
	d[src] = 0; prev[src] = -1;
	for(i = 0; i < n; i++) {
		int mind = INF, mini;
		for(j = 0; j < n; j++)
			if(mind > d[j] && !vst[j]) { mind = d[j]; mini = j; }
		if(mind == INF) break;
		vst[mini] = true;
		for(j = 0; j < n; j++)
			if(d[j] > d[mini]+next[j][mini]) { d[j] = d[mini]+next[j][mini]; prev[j] = mini; }
			else if(prev[mini] != j && d[j]+d[mini]+next[j][mini] < best) {
				best = d[j] + d[mini] + next[j][mini];
				int top = pn = 0;
				for(k = mini; k != -1; k = prev[k]) stack[top++] = k;
				while(top > 0) path[pn++] = stack[--top];
				for(k = j; k != src; k = prev[k]) path[pn++] = k;
			}
	}
}