【最短路】POJ 1847 Tram

POJ 1847 Tram

题意：给一个有向图，输入第一行分别是节点数\(n\)，起点\(a\)，终点\(b\)。下面\(n\)行，第\(i\)行的第一个数\(K_i\)表示从节点\(i\)出发所能到达的节点的个数，接下来有\(K_i\)个数，给出具体节点，其中第一个节点为默认节点，边权为0，其它节点边权为1。求从\(a\)到\(b\)的最小花费。

思路：

链式前向星建图+SPFA求最短路

有点没看清题目，误以为边的数量也最多100……maxn只设了100多一点RE了好几发，改成10000+100就AC了。

const LL INF = 0x3f3f3f3f;
const int maxn = 10000 + 100;
int num=0;
int n;
int head[maxn];
bool inq[maxn];
LL d[maxn];

struct Edge {
	int next, to;
	LL dis;
}edges[maxn];

void add_edge(int from, int to, LL dis) {
	num++;
	edges[num].next = head[from];
	edges[num].to = to;
	edges[num].dis = dis;
	head[from] = num;
}

void spfa(int s) {
	num = 0;
	queue<int>Q;
	memset(inq, 0, sizeof(inq));
	for (int i = 0; i <= n; i++) d[i] = INF;
	d[s] = 0;
	Q.push(s);
	inq[s] = true;
	while (!Q.empty()) {
		int u = Q.front(); Q.pop();
		inq[u] = false;
		for (int i = head[u]; i != 0; i = edges[i].next) {
			Edge& e = edges[i];
			if (d[u] < INF && d[u] + e.dis < d[e.to]) {
				d[e.to] = d[u] + e.dis;
				if (!inq[e.to]) {
					Q.push(e.to);
					inq[e.to] = true;
				}
			}
		}
	}
}

void solve() {
	int a, b;
	cin >> n >> a >> b;
	for (int i = 1; i <= n; i++) {
		int len;
		cin >> len;
		for (int j = 1; j <= len; j++) {
			int v;
			cin >> v;
			if (j == 1) add_edge(i, v, 0);
			else add_edge(i, v, 1);
		}
	}
	spfa(a);
	if (d[b] != INF) cout << d[b];
	else cout << -1;
}

【最短路】POJ 1847 Tram

原文：https://www.cnblogs.com/streamazure/p/13041179.html