Floyd_Warshall POJ 1847 Tram

题意:这题题目难懂.问题是A到B最少要转换几次城市.告诉每个城市相连的关系图,默认与第一个之间相连,就是不用转换,其余都要转换.

分析:把第一个城市权值设为0, 其余设为0.然后Floyd跑一下,得到A到B最少转换几次.有点水

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1e2 + 5;
const int INF = 0x3f3f3f3f;
int d[N][N];
bool vis[N];
int n, m;

void Floyd_Warshall(void)	{
	for (int k=1; k<=n; ++k)	{
		for (int i=1; i<=n; ++i)	{
			for (int j=1; j<=n; ++j)	{
				d[i][j] = min (d[i][j], d[i][k] + d[k][j]);
			}
		}
	}
}

int main(void)	{
	int A, B;
	while (scanf ("%d%d%d", &n, &A, &B) == 3)	{
		memset (d, INF, sizeof (d));
		for (int i=1; i<=n; ++i)	{
			int c;	scanf ("%d", &c);
			for (int v, j=1; j<=c; ++j)	{
				scanf ("%d", &v);
				if (j == 1)	d[i][v] = 0;
				else	d[i][v] = 1;
			}
		}
		Floyd_Warshall ();
		int ans = d[A][B];
		if (ans == INF)	ans = -1;
		printf ("%d
", ans);
	}

	return 0;
}

Floyd_Warshall POJ 1847 Tram

相关推荐