UVa 341 Non-Stop Travel

題意：
    Ruby兔中文翻譯
想法：
    用BellmanFord演算法找出最短路徑，並在找的過程中用Pre[i]紀錄什麼點走到i，最後在從終點利用Pre走回起點，並依題目輸出答案。

	#include <cstdio>
	#include <vector>
	using namespace std;
	#define Inf 99999999
	struct Edge{
	int A;
	int B;
	int Time;
	}E[100];
	int nOfE;
	int Dis[12];
	int Pre[12];
	void Initial(int &NI, int &Start);
	void BellmanFord(int &NI);
	bool Relax(Edge &E);
	void Output(int &Start, int &End);
	int main()
	{
	int NI, Start, End;
	while (scanf("%d", &NI) && NI) {
	nOfE = 0;
	for (int i = 1, n; i <= NI; ++i) {
	scanf("%d", &n);
	for (int j = 0; j < n; ++j) {
	scanf("%d %d", &E[nOfE].B, &E[nOfE].Time);
	E[nOfE++].A = i;
	}
	}
	scanf("%d %d", &Start, &End);
	Initial(NI, Start);
	BellmanFord(NI);
	Output(Start, End);
	}
	}
	void Initial(int &NI, int &Start)
	{
	for (int i = 1; i <= NI; ++i) {
	Dis[i] = Inf;
	Pre[i] = 0;
	}
	Dis[Start] = 0;
	}
	void BellmanFord(int &NI)
	{
	for (int i = 0; i < NI - 1; ++i) {
	bool change = 0;
	for (int j = 0; j < nOfE; ++j)
	if (Relax(E[j]))
	change = 1;
	if (!change)
	return;
	}
	}
	bool Relax(Edge &E)
	{
	int x = E.A;
	int y = E.B;
	if (Dis[x] + E.Time < Dis[y]){
	Dis[y] = Dis[x] + E.Time;
	Pre[y] = x;
	return true;
	}
	return false;
	}
	void Output(int &Start, int &End)
	{
	static int Case = 1;
	printf("Case %d: Path =", Case++);
	vector<int> Ans;
	int i = End;
	while (i != Start) {
	i = Pre[i];
	Ans.push_back(i);
	}
	for (int i = Ans.size() - 1; i >= 0; --i)
	printf(" %d", Ans[i]);
	printf(" %d; %d second delay\n", End, Dis[End]);
	}

view raw [UVa] 341 Non-Stop Travel.cpp hosted with ❤ by GitHub