修路: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//////////////////////////////////
906566 | hankcs | 2249: Road Construction | : Accepted | 1/1 | C++ | 00.18 s | 3304 KB | 1974 B | 2014-04-07 23:33 |
感觉有点别扭,主要是“找寻满足优先距离最短,然后费用最低的那个最低费用”的那个循环完全就是在模拟,感觉技术含量太低了。既然用了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//////////////////////////////////
906619 | hankcs | 2249: Road Construction | : Accepted | 1/1 | C++ | 00.21 s | 3724 KB | 1622 B | 2014-04-08 00:30 |
结果时间反而多了一些,大概是堆的插入排序太多了吧,本来我还写了个比较复杂的、不用visited数组的、纯dijkstra的,不过WA了,算了先这样吧,还有一堆书要看呢。
知识共享署名-非商业性使用-相同方式共享:码农场 » AOJ 2249 Road Construction 题解 《挑战程序设计竞赛》