HDU4725 The Shortest Path in Nya Graph SPFA最短路

典型的最短路问题，但是多了一个条件，就是每个点属于一个layer,相邻的layer移动，如x层移到x+1层需要花费c.

一种显而易见的转化是我把这些边都建出来，但是最后可能会使得边变成O(n^2);

网上看到的一些做法就是拆点，假如我给每层做一个平台点，所有点都可以到这个平台，然后再换乘到别的平台里不就可以了吗？所以对于属于第i层的点我们构造一个i层点的虚拟点，把这些点连到这个平台点，花费为0，相邻平台点之间的花费为c不就可以了吗？但是问题就出现在这里了，这样的话同一层的点的花费就会变成0，原本可能不可达的变得可达。网上看到的拆点方法有这么两种。

A.每层拆两个点，一个点管入，一个点管出，这样的话同层的点不会回到同层的另外一个点上。

B.每层拆一个点，这个点只管入，而处于该层的点则向左右两层点相连。

A的话新建了2n个点，4n条边（两层相邻2n,每个点对应两条边2n,2n+2n＝4n），B的话新建了n个点，5n条边（平台间2n条，每个点2n条，平台到点n条）。

不知道上面有没算错请指正。具体参考了下面的博客：

http://www.baidu.com/link?url=MV7krOHUY-l_IgU1_R5qKyUVgL5ZRprWE1IznI82Vwoo_RG_LrIaqxvCJismujP2TVaEEFg607BdhwWeUEy5aa

http://www.cnblogs.com/kuangbin/archive/2013/09/11/3315071.html

这道题当作是SPFA的模板练习题吧，晚了，睡觉去～

#pragma warning(disable:4996)

#include<iostream>

#include<cstring>

#include<string>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<queue>

#define ll long long

#define maxn 300150

#define maxm 700100

#define inf 0x3f3f3f3f

using namespace std;

int first[maxn];

int nxt[maxm];

int e;

int vv[maxm];

int cost[maxm];

int n, m, c;

int layer[maxn];

int dis[maxn];

bool in[maxn];

void addedge(int u, int v, int w)

{

	vv[e] = v; cost[e] = w;

	nxt[e] = first[u];

	first[u] = e++;

}

void spfa(int s)

{

	queue<int> q;

	memset(in, 0, sizeof(in));

	memset(dis, 0x3f, sizeof(dis));

	q.push(s); dis[s] = 0; in[s] = true;

	while (!q.empty()){

		int u = q.front(); q.pop();

		in[u] = false;

		for (int i = first[u]; i != -1; i=nxt[i]){

			int v = vv[i];

			if (dis[v] > dis[u] + cost[i]){

				dis[v] = dis[u] + cost[i];

				if (!in[v]) q.push(v), in[v] = true;

			}

		}

	}

}

int vlayer[maxn];

int main()

{

	int T; cin >> T; int ca = 0;

	while (T--)

	{

		e = 0; memset(first, -1, sizeof(first));

		memset(vlayer, 0, sizeof(vlayer));

		scanf("%d%d%d", &n, &m, &c);

		for (int i = 1; i <= n; i++){

			scanf("%d", layer + i);

			vlayer[layer[i]] = 1;

		}

		for (int i = 1; i <= n-1; i++){

			if (vlayer[i] && vlayer[i + 1]){

				addedge(n + i, n + i + 1, c);

				addedge(n + i + 1, n + i, c);

			}

		}

		for (int i = 1; i <= n; i++){

			addedge(n + layer[i], i, 0);

			if (layer[i] > 1) addedge(i, n+layer[i] - 1, c);

			if (layer[i] < n) addedge(i, n+layer[i] + 1, c);

		}

		int ui, vi, wi;

		for (int i = 0; i < m; i++){

			scanf("%d%d%d", &ui, &vi, &wi);

			addedge(ui, vi, wi);

			addedge(vi, ui, wi);

		}

		spfa(1);

		int ans = dis[n];

		if (ans<inf) printf("Case #%d: %d\n",++ca, dis[n]);

		else printf("Case #%d: %d\n", ++ca, -1);

	}

	return 0;

}

巴特西

HDU4725 The Shortest Path in Nya Graph SPFA最短路

最新文章

热门文章