UVa 10000 Longest Paths

    這題是找最長的路徑，我們可以用BellmanFord演算法，與找最短路徑相同的寫法，差別在於我們可以把點到點之間的路徑長變"負"的，最後找負最多的那個點就是最遠的點。

	#include <cstdio>
	using namespace std;
	#define Inf 9999999
	struct Edge{
	int P;
	int Q;
	}E[10005];
	int nOfE;
	int Dis[101];
	void Initial(const int &N, const int &S);
	void Input();
	void BellmanFord(const int &N);
	void Relax(const Edge &E);
	void Find_Longest_Path(const int &N, int &Min, int &pos);
	int main()
	{
	int N, S, Case = 1;
	while (scanf("%d", &N) && N)
	{
	scanf("%d", &S);
	nOfE = 0;
	Initial(N, S);
	Input();
	BellmanFord(N);
	int Min = 0, pos;
	Find_Longest_Path(N, Min, pos);
	printf("Case %d: The longest path from %d has length %d, finishing at %d.\n\n",
	Case++, S, -Min, pos);
	}
	}
	void Initial(const int &N, const int &S)
	{
	for (int i = 1; i <= N; ++i)
	Dis[i] = Inf;
	Dis[S] = 0;
	}
	void Input()
	{
	while (scanf("%d %d", &E[nOfE].P, &E[nOfE].Q)) {
	if (E[nOfE].P == 0 && E[nOfE].Q == 0)
	break;
	++nOfE;
	}
	}
	void BellmanFord(const int &N)
	{
	for (int time = 0; time < N - 1; ++time)
	for (int i = 0; i < nOfE; ++i)
	Relax(E[i]);
	}
	void Relax(const Edge &E)
	{
	int p = E.P;
	int q = E.Q;
	if (Dis[p] - 1 < Dis[q])
	Dis[q] = Dis[p] - 1;
	}
	void Find_Longest_Path(const int &N, int &Min, int &pos)
	{
	for (int i = 1; i <= N; ++i)
	if (Dis[i] < Min) {
	Min = Dis[i];
	pos = i;
	}
	}

view raw [UVa] 10000 Longest Paths.cpp hosted with ❤ by GitHub