HDU 4725(最短路之建图难点)

题意：n个点，每个点属于特定一层，相邻的两层之间距离固定是c，另有额外m条边，然后求1到n的最短路径，没有则输出-1。

思路：建图时出现了一点问题，SPFA和DJ都一直TLE，我原本的错误思路是：将每一层抽象出来，对应为n+1...n+n，然后读每个点所在层flo时，使i和第n+flo建边(双向边)，然后通过一个vis数组标记第i层是否出现过，然后再对同时出现的相邻两层进行建边，本感觉思路恰好，肯定能过，但这样建图会存在一个问题，会导致同一层的所有点之间的距离均为1！！所以同一层的点如果想通过层到达，需要先到别的层，再回来此层。

所以建图时可直接建一个从第flo层到点i的单向边表示可从flo层回到i，加两条i到邻层的单向边(邻层存在则建，不存在不建)，表示i通过层的关系到达邻层的点，同时也要建层与层之间的边，原因：当上一层的点到达该层，此时可以走0距离走向该层的点，也可走c距离再向下一层走。

完整思路：层与层建边，点与点建边，层与在该层上的点建边 （边长为0），点与相邻层(存在的相邻层)建边 （边长为c）。避免了拆点的思路（拆点方法可看kuangbin的博客园）。

代码1

#include <algorithm>
#include <iostream>
#include <string.h>
#include <cstdio>
#include <queue>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+5;
struct node
{
	int v, w, next;
}edge[maxn*8];
int n, m, c, no;
int head[maxn*2], book[maxn*2], dis[maxn*2], flr[maxn], vis[maxn];
queue<int> q;
void init()
{
	no = 0;
	memset(book, 0, sizeof book);
	memset(dis, 0x3f, sizeof dis);
	memset(head, -1, sizeof head);
	memset(vis, 0, sizeof vis);
}
void add(int u, int v, int w)
{
	edge[no].v = v;
	edge[no].w = w;
	edge[no].next = head[u];
	head[u] = no++;
}
int SPFA(int s, int t)
{
	while(!q.empty()) q.pop();
	dis[s] = 0;
	q.push(s);
	book[s] = 1;
	while(!q.empty())
	{
		int tp = q.front(); q.pop();
		book[tp] = 0;
		int k = head[tp];
		while(k != -1)
		{
			if(dis[edge[k].v] > dis[tp] + edge[k].w)
			{
				dis[edge[k].v] = dis[tp] + edge[k].w;
				if(book[edge[k].v] == 0)
				{
					book[edge[k].v] = 1;
					q.push(edge[k].v);
				}
			}
			k = edge[k].next;
		}
	}
	if(dis[t] == inf) return -1;
	return dis[t];
}
int main()
{
	int t, flo, u, v, w;
	scanf("%d", &t);
	for(int l = 1; l <= t; ++l)
	{
		scanf("%d %d %d", &n, &m, &c);
		init();
		for(int i = 1; i <= n; ++i)
		{
			scanf("%d", &flo);
			flr[i] = flo;
			vis[flo] = 1;
		}
		for(int i = 2; i <= n; ++i)
		{
			if(vis[i] && vis[i-1]) 
			{
				add(n+i, n+i-1, c);
				add(n+i-1, n+i, c);
			}
		}
		for(int i = 1; i <= n; ++i)
		{
			add(n+flr[i], i, 0);
			if(vis[flr[i]-1]) add(i, n+flr[i]-1, c);
			if(vis[flr[i]+1]) add(i, n+flr[i]+1, c);
		}
		for(int i = 1; i <= m; ++i)
		{
			scanf("%d %d %d", &u, &v, &w);
			add(u, v, w);
			add(v, u, w);
		}
		printf("Case #%d: %d\n", l, SPFA(1, n));
	}
	return 0;
}

代码2

#include <algorithm>
#include <iostream>
#include <string.h>
#include <cstdio>
#include <queue>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+5;
struct node
{
	int v, w, next;
	bool operator<(const node k) const
	{
		return w > k.w;
	}
}edge[maxn*8];
int n, m, c, no;
int head[maxn*2], book[maxn*2], dis[maxn*2], flr[maxn], vis[maxn];
priority_queue<node> q;
void init()
{
	no = 0;
	memset(book, 0, sizeof book);
	memset(dis, 0x3f, sizeof dis);
	memset(head, -1, sizeof head);
	memset(vis, 0, sizeof vis);
}
void add(int u, int v, int w)
{
	edge[no].v = v;
	edge[no].w = w;
	edge[no].next = head[u];
	head[u] = no++;
}
int DJ(int s, int t)
{
	while(!q.empty()) q.pop();
	dis[s] = 0;
	q.push((node){s, 0, -1});
	while(!q.empty())
	{
		node tp = q.top(); q.pop();
		if(book[tp.v]) continue;
		book[tp.v] = 1;
		int k = head[tp.v];
		while(k != -1)
		{
			if(dis[edge[k].v] > dis[tp.v] + edge[k].w)
			{
				dis[edge[k].v] = dis[tp.v] + edge[k].w;
				q.push((node){edge[k].v, dis[edge[k].v], -1});
			}
			k = edge[k].next;
		}
	}
	if(dis[t] == inf) return -1;
	return dis[t];
}
int main()
{
	int t, flo, u, v, w;
	scanf("%d", &t);
	for(int l = 1; l <= t; ++l)
	{
		scanf("%d %d %d", &n, &m, &c);
		init();
		for(int i = 1; i <= n; ++i)
		{
			scanf("%d", &flo);
			flr[i] = flo;
			vis[flo] = 1;

		}
		for(int i = 2; i <= n; ++i)
		{
			if(vis[i] && vis[i-1]) 
			{
				add(n+i, n+i-1, c);
				add(n+i-1, n+i, c);
			}
		}
		for(int i = 1; i <= n; ++i)
		{
			add(n+flr[i], i, 0);
            if(flr[i] > 1) add(i, n+flr[i]-1, c);
            if(flr[i] < n) add(i, n+flr[i]+1, c);
		}
		for(int i = 1; i <= m; ++i)
		{
			scanf("%d %d %d", &u, &v, &w);
			add(u, v, w);
			add(v, u, w);
		}
		printf("Case #%d: %d\n", l, DJ(1, n));
	}
	return 0;
}