- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我目前正在 Codechef 处理一个问题.您可以在此处找到问题陈述: Delivery Boy
简而言之,问题是要求查询 n
次从 start
到 end
的最短路径。我的解决方案是将 Dijsktra
与 priority_queue
一起使用,并将结果缓存到 hash_map
中,以防我们已经有了一个 start
.不幸的是,我多次遇到 time limit exceed
并且我找不到更好的方法来让它更快。我想知道我是否在正确的轨道上?或者有更好的算法来解决这个问题?
顺便说一句,由于比赛仍在进行中,请不要发布任何解决方案。一个提示对我来说绰绰有余。谢谢。
这是我的尝试:
#ifdef __GNUC__
#include <ext/hash_map>
#else
#include <hash_map>
#endif
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <utility>
#include <stack>
#include <deque>
#include <queue>
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
using namespace std;
#ifdef __GNUC__
namespace std {
using namespace __gnu_cxx;
}
#endif
const int MAX_VERTICES = 250;
const int INFINIY = (1 << 28);
int weight[MAX_VERTICES + 1][MAX_VERTICES + 1];
bool visited_start[MAX_VERTICES + 1] = { 0 };
struct vertex {
int node;
int cost;
vertex(int node = 0, int cost = 0)
: node(node), cost(cost) {
}
bool operator <(const vertex& rhs) const {
return cost < rhs.cost;
}
bool operator >(const vertex& rhs) const {
return cost > rhs.cost;
}
};
hash_map<int, vector<vertex> > cache;
typedef priority_queue<vertex, vector<vertex>, greater<vertex> > min_pq;
vector<vertex> dijkstra_compute_path(int start, int n) {
min_pq pq;
vector<vertex> path;
vector<int> visited(n, 0);
int min_cost = 0;
int better_cost;
vertex u;
for (int i = 0; i < n; ++i) {
path.push_back(vertex(i, INFINIY));
}
path[start].cost = 0;
pq.push(vertex(start, path[start].cost));
while (!pq.empty()) {
// extract min cost
u = pq.top();
pq.pop();
// mark it as visited
visited[u.node] = 1;
// for each vertex v that is adjacent to u
for (int v = 0; v < n; ++v) {
// if it's not visited, visit it
if (visited[v] == 0) {
better_cost = path[u.node].cost + weight[u.node][v];
// update cost
if (path[v].cost > better_cost) {
path[v].cost = better_cost;
pq.push(vertex(v, path[v].cost));
}
}
}
}
return path;
}
void check_in_cache(vector<vertex>& path, int start, int no_street) {
if (visited_start[start] == 0) {
path = dijkstra_compute_path(start, no_street);
cache.insert(make_pair(start, path));
visited_start[start] = 1;
}
else {
path = cache[start];
}
}
void display_cost(int stop_at_gas_cost, int direct_cost) {
printf("%d ", stop_at_gas_cost);
if (stop_at_gas_cost > direct_cost) {
printf("%d\n", stop_at_gas_cost - direct_cost);
}
else {
printf("0\n");
}
}
void handle_case_one() {
int no_scenario;
int dummy;
int s, g, d;
scanf("%d", &dummy);
scanf("%d", &no_scenario);
for (int i = 0; i < no_scenario; ++i) {
scanf("%d %d %d", &s, &g, &d);
printf("0 0\n");
}
}
void inout_delivery_boy() {
int no_street;
int no_scenario;
int restaurant;
int gas_station;
int destination;
int stop_at_gas_cost;
int direct_cost;
vector<vertex> direct;
vector<vertex> indirect;
vector<vertex> d;
int c;
scanf("%d", &no_street);
if (no_street == 1) {
handle_case_one();
return;
}
for (int x = 0; x < no_street; ++x) {
for (int y = 0; y < no_street; ++y) {
scanf("%d", &c);
weight[x][y] = c;
}
}
for (int i = 0; i < no_street; ++i) {
d.push_back(vertex(i, INFINIY));
}
scanf("%d", &no_scenario);
for (int i = 0; i < no_scenario; ++i) {
scanf("%d %d %d", &restaurant, &gas_station, &destination);
// check in cache
check_in_cache(direct, restaurant, no_street);
check_in_cache(indirect, gas_station, no_street);
// calculate the cost
stop_at_gas_cost = direct[gas_station].cost + indirect[destination].cost;
direct_cost = direct[destination].cost;
// output
display_cost(stop_at_gas_cost, direct_cost);
}
}
void dijkstra_test(istream& in) {
int start;
int no_street;
int temp[4] = { 0 };
vector<vertex> path;
in >> no_street;
for (int x = 0; x < no_street; ++x) {
for (int y = 0; y < no_street; ++y) {
in >> weight[x][y];
}
}
// arrange
start = 0;
temp[0] = 0;
temp[1] = 2;
temp[2] = 1;
temp[3] = 3;
// act
path = dijkstra_compute_path(start, no_street);
// assert
for (int i = 0; i < no_street; ++i) {
assert(path[i].cost == temp[i]);
}
// arrange
start = 1;
temp[0] = 1;
temp[1] = 0;
temp[2] = 2;
temp[3] = 4;
// act
path = dijkstra_compute_path(start, no_street);
// assert
for (int i = 0; i < no_street; ++i) {
assert(path[i].cost == temp[i]);
}
// arrange
start = 2;
temp[0] = 2;
temp[1] = 1;
temp[2] = 0;
temp[3] = 3;
// act
path = dijkstra_compute_path(start, no_street);
// assert
for (int i = 0; i < no_street; ++i) {
assert(path[i].cost == temp[i]);
}
// arrange
start = 3;
temp[0] = 1;
temp[1] = 1;
temp[2] = 1;
temp[3] = 0;
// act
path = dijkstra_compute_path(start, no_street);
// assert
for (int i = 0; i < no_street; ++i) {
assert(path[i].cost == temp[i]);
}
}
int main() {
// ifstream inf("test_data.txt");
// dijkstra_test(inf);
inout_delivery_boy();
return 0;
}
最佳答案
请注意问题中 N 很小。你试过弗洛伊德最短路径算法来预先计算每两个节点之间的最短路径吗?会耗费O(N^3)的时间,也就是问题中的250^3=15625000,应该很容易在1秒内跑完。然后您可以在 O(1) 中回答每个查询。
弗洛伊德简介:
http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
ps:我认为缓存的 dijstra 对整个测试用例的最大运行时间也是 O(N^3)。但是你实现缓存的方式会花费更多不必要的时间在内存复制上,这可能会导致 TLE。只是一个猜测。
关于algorithm - 查询n次时如何改进Dijkstra算法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11772554/
我有三张 table 。表 A 有选项名称(即颜色、尺寸)。表 B 有选项值名称(即蓝色、红色、黑色等)。表C通过将选项名称id和选项名称值id放在一起来建立关系。 我的查询需要显示值和选项的名称,而
在mysql中,如何计算一行中的非空单元格?我只想计算某些列之间的单元格,比如第 3-10 列之间的单元格。不是所有的列...同样,仅在该行中。 最佳答案 如果你想这样做,只能在 sql 中使用名称而
关闭。这个问题需要多问focused 。目前不接受答案。 想要改进此问题吗?更新问题,使其仅关注一个问题 editing this post . 已关闭 7 年前。 Improve this ques
我正在为版本7.6进行Elasticsearch查询 我的查询是这样的: { "query": { "bool": { "should": [ {
关闭。这个问题需要多问focused 。目前不接受答案。 想要改进此问题吗?更新问题,使其仅关注一个问题 editing this post . 已关闭 7 年前。 Improve this ques
是否可以编写一个查询来检查任一子查询(而不是一个子查询)是否正确? SELECT * FROM employees e WHERE NOT EXISTS (
我找到了很多关于我的问题的答案,但问题没有解决 我有表格,有数据,例如: Data 1 Data 2 Data 3
以下查询返回错误: 查询: SELECT Id, FirstName, LastName, OwnerId, PersonEmail FROM Account WHERE lower(PersonEm
以下查询返回错误: 查询: SELECT Id, FirstName, LastName, OwnerId, PersonEmail FROM Account WHERE lower(PersonEm
我从 EditText 中获取了 String 值。以及提交查询的按钮。 String sql=editQuery.getText().toString();// SELECT * FROM empl
我有一个或多或少有效的查询(关于结果),但处理大约需要 45 秒。这对于在 GUI 中呈现数据来说肯定太长了。 所以我的需求是找到一个更快/更高效的查询(几毫秒左右会很好)我的数据表大约有 3000
这是我第一次使用 Stack Overflow,所以我希望我以正确的方式提出这个问题。 我有 2 个 SQL 查询,我正在尝试比较和识别缺失值,尽管我无法将 NULL 字段添加到第二个查询中以识别缺失
什么是动态 SQL 查询?何时需要使用动态 SQL 查询?我使用的是 SQL Server 2005。 最佳答案 这里有几篇文章: Introduction to Dynamic SQL Dynami
include "mysql.php"; $query= "SELECT ID,name,displayname,established,summary,searchlink,im
我有一个查询要“转换”为 mysql。这是查询: select top 5 * from (select id, firstName, lastName, sum(fileSize) as To
通过我的研究,我发现至少从 EF 4.1 开始,EF 查询上的 .ToString() 方法将返回要运行的 SQL。事实上,这对我来说非常有用,使用 Entity Framework 5 和 6。 但
我在构造查询来执行以下操作时遇到问题: 按activity_type_id过滤联系人,仅显示最近事件具有所需activity_type_id或为NULL(无事件)的联系人 表格结构如下: 一个联系人可
如何让我输入数据库的信息在输入数据 5 分钟后自行更新? 假设我有一张 table : +--+--+-----+ |id|ip|count| +--+--+-----+ |
我正在尝试搜索正好是 4 位数字的 ID,我知道我需要使用 LENGTH() 字符串函数,但找不到如何使用它的示例。我正在尝试以下(和其他变体)但它们不起作用。 SELECT max(car_id)
我有一个在 mysql 上运行良好的 sql 查询(查询 + 连接): select sum(pa.price) from user u , purchase pu , pack pa where (
我是一名优秀的程序员,十分优秀!