2062.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2062 on 2006-02-17 at 01:09:36 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 128;
const int INF = 60000000;

int N, M, next[MAX][MAX], prev[MAX];

int Dijkstra(int, int, bool);

int main()
{
	int i, j;
	
	while(scanf("%d %d", &N, &M) != EOF && N != 0) {
		for(i = 1; i <= N; i++)
			for(j = 1; j <= N; j++)
				next[i][j] = INF;
		for(i = 0; i < M; i++) {
			int x, y, d;
			scanf("%d %d %d", &x, &y, &d);
			next[x][y] = next[y][x] = d;
		}
		int fir = Dijkstra(1, N, true), sec = INF;
		bool diff = true;
		if(fir == INF) diff = false;
		else {
			for(j = N; j != 1; j = prev[j]) {
				int d = next[j][prev[j]];
				next[j][prev[j]] = next[prev[j]][j] = INF;
				sec = min(sec, Dijkstra(1, N, false));
				if(sec == fir) break;
				next[j][prev[j]] = next[prev[j]][j] = d;
			}
			if(sec == INF) diff = false;
		}
		if(diff) printf("%d %d\n", fir, sec);
		else printf("Sorry, no different ways available.\n");
	}
	
	return 0;
}


int Dijkstra(int src, int dis, bool m)
{
	int i, j, d[MAX], mind, mini;
	bool tran[MAX] = { false };
	
	for(i = 1; i <= N; i++) d[i] = INF;
	d[src] = 0;
	for(i = 0; i < N; i++) {
		mind = INF;
		for(j = 1; j <= N; j++)
			if(d[j] < mind && !tran[j]) mind = d[j], mini = j;
		if(mind == INF) break;
		else {
			tran[mini] = true;
			for(j = 1; j <= N; j++)
				if(!tran[j] && next[mini][j] + d[mini] < d[j]) {
					d[j] = next[mini][j] + d[mini];
					if(m) prev[j] = mini;
				}
			if(mini == dis) break;
		}
	}
	
	return d[dis];
}