POJ 3268 Silver Cow Party 题解 《挑战程序设计竞赛》

POJ 3268 Silver Cow Party

奶牛派对：有分别来自 N 个农场的 N 头牛去农场 X 嗨皮，农场间由 M 条有向路径连接。每头牛来回都挑最短的路走，求它们走的路的最大长度？

2.5 它们其实都是“图”

最短路 dijkstra 解决任意两点最短路的变种

用warshall_floyd的话会TLE，1000³复杂度果然不是盖的，另外X的编号记得减一，测试用例很恶心的，即使忘了减一也照样得出正确答案10，但是一提交就WA，让我深深地感到了来自命题者的恶意：

#ifndef ONLINE_JUDGE
#pragma warning(disable : 4996)
#endif
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX_V 1024
int d[MAX_V][MAX_V];	//	d[u][v]表示边e=(u,v)的权值，不存在的时候等于无穷大或者d[i][i] = 0
int V;					//	顶点数

void warshall_floyd()
{
	for (int k = 0; k < V; ++k)
	{
		for (int i = 0; i < V; ++i)
		{
			for (int j = 0; j < V; ++j)
			{
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int M, X;
	cin >> V >> M >> X;
	--X
	memset(d, 0x3f, V * MAX_V * sizeof(int));
	for (int i = 0; i < V; ++i)
	{
		d[i][i] = 0;
	}
	while (M--)
	{
		int A, B, T;
		cin >> A >> B >> T;
		--A;
		--B;
		d[A][B] = T;
	}
	warshall_floyd();
	int ans = 0;
	for (int i = 0; i < V; ++i)
	{
		ans = max(ans, d[i][X] + d[X][i]);
	}
	cout << ans << endl;
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

dijkstra是解决单源最短路问题的，稍微修改一下就可以支持任意两点最短路：

#ifndef ONLINE_JUDGE
#pragma warning(disable : 4996)
#endif
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
using namespace std;
#define MAX_V 1024

// 从顶点from指向顶点to的权值为cost的边
struct edge
{
	int to, cost;
	edge(){}
	edge(int to, int cost) : to(to), cost(cost){}
};

// first 最短路径，second顶点编号
typedef pair<int, int> P;

// 图
vector<edge>  G[MAX_V];

// 最短距离
int d[MAX_V][MAX_V];
// V是顶点数，E是边数
int V, E;

// 求解从顶点s出发到所有点的最短距离
void dijkstra(int s)
{
	priority_queue<P, vector<P>, greater<P> > que;
	memset(d[s], 0x3f, MAX_V * sizeof(int));
	d[s][s] = 0;
	que.push(P(0, s));

	while (!que.empty())
	{
		P p = que.top(); que.pop();
		int v = p.second;
		if (d[s][v] < p.first) continue;
		for (int i = 0; i < G[v].size(); ++i)
		{
			edge e = G[v][i];
			if (d[s][e.to] > d[s][v] + e.cost)
			{
				d[s][e.to] = d[s][v] + e.cost;
				que.push(P(d[s][e.to], e.to));
			}
		}
	}
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int M, X;
	cin >> V >> M >> X;
	--X;
	while (M--)
	{
		int A, B, T;
		cin >> A >> B >> T;
		--A;
		--B;
		G[A].push_back(edge(B, T));
	}
	for (int i = 0; i < V; ++i)
	{
		dijkstra(i);
	}

	int ans = 0;
	for (int i = 0; i < V; ++i)
	{
		if (i == X)
		{
			continue;
		}
		ans = max(ans, d[i][X] + d[X][i]);
	}

	cout << ans << endl;
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

不过上面那个实在太浪费，我只想计算起点或终点是X的路径最短路问题，可以在上面while (!que.empty())的循环里加入判断条件，还可以这么玩：

来一个反向图，交换边的起点和终点得到反向的有向图，两次dijkstra解决问题：

#ifndef ONLINE_JUDGE
#pragma warning(disable : 4996)
#endif
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
using namespace std;
#define MAX_V 10240

// 从顶点from指向顶点to的权值为cost的边
struct edge
{
	int to, cost;
	edge(){}
	edge(int to, int cost) : to(to), cost(cost){}
};

// first 最短路径，second顶点编号
typedef pair<int, int> P;

// 图
vector<vector<edge> > G(MAX_V);
// 反向图
vector<vector<edge> > RG(MAX_V);

// 最短距离
int d[MAX_V];
int rd[MAX_V];
// V是顶点数，E是边数
int V, E;

// 求解从顶点s出发到所有点的最短距离
void dijkstra(int s)
{
	priority_queue<P, vector<P>, greater<P> > que;
	memset(d, 0x3f, sizeof(d));
	d[s] = 0;
	que.push(P(0, s));

	while (!que.empty())
	{
		P p = que.top(); que.pop();
		int v = p.second;
		if (d[v] < p.first) continue;
		for (int i = 0; i < G[v].size(); ++i)
		{
			edge e = G[v][i];
			if (d[e.to] > d[v] + e.cost)
			{
				d[e.to] = d[v] + e.cost;
				que.push(P(d[e.to], e.to));
			}
		}
	}
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int M, X;
	cin >> V >> M >> X;
	--X;
	while (M--)
	{
		int A, B, T;
		cin >> A >> B >> T;
		--A;
		--B;
		G[A].push_back(edge(B, T));
		RG[B].push_back(edge(A, T));
	}
	dijkstra(X);
	G = RG;
	memcpy(rd, d, sizeof(d));
	dijkstra(X);
	for (int i = 0; i < V; ++i)
	{
		d[i] += rd[i];
	}

	cout << *max_element(d, d + V) << endl;
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 3268 Silver Cow Party 题解 《挑战程序设计竞赛》