学步园

这是我在学习图论时一本参考资料上的例题，觉得有趣就写了写。

题目大意请进：胡老师的跨国逃亡

大概思路：第一次我思考时，首先是找到A国中的边界点，然后找出1到边界点距离的最小值，然后通过通过spfa枚举边界点的去找离2的最小值，但这样应该会超时。于是我将地图预处理了一下，首先找到1离A中所有的点的最短路，然后去找2离B中所有的点的最短路。这里需要注意一下的就是怎么样去保证d[i]一定是代表一个国家之内的最小值，这里我们可以加一个判断，即vis[v] == f。记得把初始值d[src]置为0，这样，我们最后求得的距离一定是国家与国家之间的最小值。
  怎么去找边界点呢？我们可以另外开一个数组来存储边，这样只要vis[u] != vis[v]的话，说明它就是边界点，由于d[i]一定代表国家与国家之间的最小值，然后通过枚举判断最小值即可。

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <map>
#include <queue>
using namespace std;

const int MAXN = 3010;
const int MAXM = 500510;
const int INF = 0x3f3f3f3f;

struct Edge
{
	int u, v, w;
	int next;
}edge[MAXN], Save[MAXN]; 
               //Save储存边的值
int n, m;
int cnt;

int first[MAXN], d[MAXN];
int vis[MAXN];

void init()
{
	cnt = 0;
	memset(first, -1, sizeof(first));
	memset(vis, 0, sizeof(vis));
	memset(d, INF, sizeof(d));
}

void read_graph(int u, int v, int w)
{
	edge[cnt].v = v, edge[cnt].w = w;
	edge[cnt].next = first[u], first[u] = cnt++;
}

void read_case()
{
	init();
	for(int i = 1; i <= m; i++)
	{
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		read_graph(u, v, w);
		read_graph(v, u, w);
		Save[i].u = u, Save[i].v = v, Save[i].w = w;
	}
	int f;
	for(int i = 1; i <= n; i++)
	{
		scanf("%d", &f);
		vis[i] = f;
	}
}

void spfa(int src, int f)
{
	queue<int> q;
	bool inq[MAXN] = {0};
	d[src] = 0;   //初始点需要置0 
	q.push(src);
	while(!q.empty())
	{
		int x = q.front(); q.pop();
		inq[x] = 0;
		for(int e = first[x]; e != -1; e = edge[e].next)
		{
			int v = edge[e].v, w = edge[e].w;
			if(d[v] > d[x] + w && vis[v] == f) //枚举每个A或者B国家中到源点的最短距离
			{
				d[v] = d[x] + w;
				if(!inq[v])
				{
					inq[v] = 1;
					q.push(v);
				}
			}
		}
	}
}

void solve()
{
	int ans = INF;
	read_case();
	spfa(1, 1);
	spfa(2, 2);
	for(int i = 1; i <= m; i++)
	{
		int u = Save[i].u, v = Save[i].v, w = Save[i].w; //储存边，枚举时需要用到 
		if(vis[u] != vis[v])
		{
			if(d[u] + d[v] + w < ans)
			{
				ans = d[u] + d[v] + w;
			}
		}
	}
	if(ans < INF)
	{
		printf("%d\n", ans);
	}
	else printf("-1\n");
}

int main()
{
	while(~scanf("%d%d", &n, &m))
	{
		solve();
	}
	return 0;
}