AOJ 2249 Road Construction 题解 《挑战程序设计竞赛》

AOJ 2249 Road Construction

修路：ACM之王要在全国改造交通网络，第一保证首都最短路，第二保证最低花费。

2.5 它们其实都是“图”

最短路 dijkstra 

ACM-ICPC Japan的一道题，dijkstra 条件复杂化变种而已。先满足最短路，然后再满足最低花费。

第一种解法

#include <iostream>
#include <queue>
#include <functional>
#include <cstring>
using namespace std;
#define MAX_V 10240

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

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

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

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

// 求解从顶点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.distance)
			{
				d[e.to] = d[v] + e.distance;
				que.push(P(d[e.to], e.to));
			}
		}
	}
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{

	int /*N = V,*/ M;
	while (cin >> V >> M && V)
	{
		for (int i = 0; i < V; ++i)
		{
			G[i].clear();
		}
		for (int i = 0; i < M; ++i)
		{
			int u, v, d, c;
			cin >> u >> v >> d >> c;
			--u, --v;
			G[u].push_back(edge(v, d, c));
			G[v].push_back(edge(u, d, c));
		}
		// 首都是0号
  		dijkstra(0);
		int ans = 0;
		for (int i = 1; i < V; ++i)
		{
			int min_cost = 0x3f3f3f3f;
			// 找寻满足优先距离最短，然后费用最低的那个最低费用
			for (int j = 0; j < G[i].size(); ++j)
			{
				if (d[G[i][j].to] + G[i][j].distance == d[i] && G[i][j].cost < min_cost)
				{
					min_cost = G[i][j].cost;
				}
			}
			ans += min_cost;
		}
		cout << ans << endl;
	}

	return 0;
}
///////////////////////////End Sub//////////////////////////////////

感觉有点别扭，主要是“找寻满足优先距离最短，然后费用最低的那个最低费用”的那个循环完全就是在模拟，感觉技术含量太低了。既然用了dijkstra，那就把它用到极致吧！

#include <iostream>
#include <queue>
#include <functional>
#include <cstring>
using namespace std;
#define MAX_V 10240

// 从顶点from指向顶点to的权值为cost的边
typedef struct edge
{
	int to, distance, cost;
	edge(){}
	edge(int to, int distance, int cost) : to(to), distance(distance), cost(cost){}
	bool operator > (const edge & b) const
	{
		return distance != b.distance ? distance > b.distance : cost > b.cost;
	}
} P;

// first 最短路径，second顶点编号

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

// V是顶点数
int V;
bool visited[MAX_V];

// 求解从顶点s出发到所有点的最短花费
int dijkstra(int s)
{
	int result = 0;
	priority_queue<P, vector<P>, greater<P> > que;
	memset(visited, 0, V * sizeof(bool));
	que.push(P(0, 0, 0));

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

	return result;
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
	int /*N = V,*/ M;
	while (cin >> V >> M && V)
	{
		for (int i = 0; i < V; ++i)
		{
			G[i].clear();
		}
		for (int i = 0; i < M; ++i)
		{
			int u, v, d, c;
			cin >> u >> v >> d >> c;
			--u, --v;
			G[u].push_back(edge(v, d, c));
			G[v].push_back(edge(u, d, c));
		}

		cout << dijkstra(0) << endl;
	}
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

结果时间反而多了一些，大概是堆的插入排序太多了吧，本来我还写了个比较复杂的、不用visited数组的、纯dijkstra的，不过WA了，算了先这样吧，还有一堆书要看呢。

 知识共享署名-非商业性使用-相同方式共享：码农场 » AOJ 2249 Road Construction 题解 《挑战程序设计竞赛》