POJ 2387 Til the Cows Come Home

這題其實就是要求終點走到起點的最短路徑，因此用個簡單的BellmanFord演算法即可解決這題。

	#include <cstdio>
	using namespace std;
	#define Inf 99999999
	struct Edge{
	int x;
	int y;
	int Len;
	}E[2001];
	int Dis[1001];
	void Initial(const int &N);
	void BellmanFord(const int &N, const int &T);
	bool Relax(const Edge &E);
	int main()
	{
	int T, N;
	while (scanf("%d %d", &T, &N) != EOF)
	{
	Initial(N);
	for (int i = 0; i < T; ++i)
	scanf("%d %d %d", &E[i].x, &E[i].y, &E[i].Len);
	BellmanFord(N, T);
	printf("%d\n", Dis[1]);
	}
	}
	void Initial(const int &N)
	{
	Dis[N] = 0;
	for (int i = 1; i < N; ++i)
	Dis[i] = Inf;
	}
	void BellmanFord(const int &N, const int &T)
	{
	for (int times = 0; times < N - 1; ++times){
	bool NotOK = 0;
	for (int i = 0; i < T; ++i)
	if (Relax(E[i])) NotOK = 1;
	if (!NotOK) return;
	}
	}
	bool Relax(const Edge &E)
	{
	bool change = 0;
	if (Dis[E.x] + E.Len < Dis[E.y]){
	Dis[E.y] = Dis[E.x] + E.Len;
	change = 1;
	}
	if (Dis[E.y] + E.Len < Dis[E.x]){
	Dis[E.x] = Dis[E.y] + E.Len;
	change = 1;
	}
	return change;
	}

view raw [POJ] 2387 Til the Cows Come Home.cpp hosted with ❤ by GitHub