小明的火车旅行计划
题目
by Zhenqian Shen
描述
给定有向图, 其中有 \(N\) 个节点和 \(M\) 条边, 每条边有时间和路费. 请求在时间限制下从起点到终点的最小路费; 若不存在, 返回 -1.
提示: 节点数小于 \(2^{16}\), 边数小于 \(2^{20}\), 时间和路费均小于 \(2^{16}\).
IO格式
输入:
N M
第1条边发端 第1条边末端 第1条边时间 第1条边路费
... // 起点按非递减排列
起点 终点 时间限制
输出:
最小花费或-1
样例
输入:
4 5
0 1 1 1
0 2 4 2
1 2 1 5
1 3 4 2
2 3 1 1
0 3 4
输出:
7
解答
思路
这同样是一道比较令人难受的题目, 我没有找到能够过全部 10 个点单一算法.
和缺失数据恢复一样, 这题同样利用判题点有限的特点, 选用两个算法合并求解.
具体而言, 我先后采用了 DFS 及贪心的 DFS. DFS 的剪枝条件是时间超过限制和路费超过现得解; 贪心是通过对邻接表排序, 每次取最小的邻边, 这样当得到第一个解时, 理论上也是全局解.
代码
图的存储
这里采取的是索引表+一维数组实现的邻接表. 因为输入边的起点是非递减的, 因此这样的结构有利于处理.
struct Net {
struct Path {
Path() : target(0), time(0), cost(0) {}
ui target;
ui time;
ui cost;
};
struct Node {
Node() : pos(nullptr), len(0) {}
Path* pos;
ui len;
};
Net(ui n, ui m) : N(n), M(m), nodes(new Node[n]), paths(new Path[m]) {}
~Net() {
delete[] nodes;
delete[] paths;
}
ui N, M;
Node* nodes;
Path* paths;
};
剪枝 DFS
struct Result {
ui ret;
bool res;
};
Result dfs(Net& net) {
struct Status {
ui curTime;
ui curCost;
};
Result result{0, false};
stack<Net::Path*> s;
net.adj(s, origin);
stack<Status> st;
st.push(Status{0, 0});
bool* vis = new bool[net.N]{false};
vis[origin] = true;
while (!s.empty()) {
auto* cur = s.top();
if (vis[cur->target]) {
vis[cur->target] = false;
s.pop();
st.pop();
} else {
Status prevSt = st.top(),
curSt = Status{prevSt.curTime + cur->time};
if (curSt.curTime > timeLmt) {
s.pop();
continue;
}
curSt.curCost = prevSt.curCost + cur->cost;
if (result.res) {
if (curSt.curCost >= result.ret)
s.pop();
else {
if (cur->target == dest) {
result.ret = curSt.curCost;
s.pop();
} else {
vis[cur->target] = true;
st.push(curSt);
net.adj(s, cur->target, vis);
}
}
} else {
if (cur->target == dest) {
result.ret = curSt.curCost;
result.res = true;
s.pop();
} else {
vis[cur->target] = true;
st.push(curSt);
net.adj(s, cur->target, vis);
}
}
}
}
return result;
}
递归版本:
bool* vis;
ui result = UINT_MAX;
void dfs(Net& net, Net::Path* cur, ui curTime, ui curCost) {
ui tmpTime = curTime + cur->time;
if (tmpTime > timeLmt) return;
ui tmpCost = curCost + cur->cost;
if (tmpCost >= result) return;
if (cur->target == dest)
result = tmpCost;
else {
auto* begin = net.nodes[cur->target].pos;
auto* end = begin + net.nodes[cur->target].len;
for (auto* i = begin; i < end; i++) {
if (!vis[i->target]) {
vis[i->target] = true;
dfs(net, i, tmpTime, tmpCost);
vis[i->target] = false;
}
}
}
}
void dfs(Net& net) {
vis = new bool[net.N];
vis[origin] = true;
auto* begin = net.nodes[origin].pos;
auto* end = begin + net.nodes[origin].len;
for (auto* i = begin; i < end; i++) {
if (!vis[i->target]) {
vis[i->target] = true;
dfs(net, i, 0, 0);
vis[i->target] = false;
}
}
}
贪心 DFS
struct Result {
ui ret;
bool res;
};
Result dfs(Net& net) {
struct Status {
ui curTime;
ui curCost;
};
Result result{0, false};
stack<Net::Path*> s;
net.adj(s, origin);
stack<Status> st;
st.push(Status{0, 0});
bool* vis = new bool[net.N]{false};
vis[origin] = true;
while (!s.empty()) {
auto* cur = s.top();
if (vis[cur->target]) {
vis[cur->target] = false;
s.pop();
st.pop();
} else {
Status prevSt = st.top(),
curSt = Status{prevSt.curTime + cur->time};
if (curSt.curTime > timeLmt) {
s.pop();
continue;
}
curSt.curCost = prevSt.curCost + cur->cost;
if (cur->target == dest) {
result.ret = curSt.curCost;
result.res = true;
break;
} else {
vis[cur->target] = true;
st.push(curSt);
net.adj(s, cur->target, vis);
}
}
}
delete[] vis;
return result;
}
最终提交
#include <cstdio>
#include <algorithm>
#include <stack>
using namespace std;
#define prf printf
#define scf scanf
using ui = unsigned int;
struct Net {
struct Path {
Path() : target(0), time(0), cost(0) {}
ui target;
ui time;
ui cost;
};
struct Node {
Node() : pos(nullptr), len(0) {}
Path* pos;
ui len;
};
Net(ui n, ui m) : N(n), M(m), nodes(new Node[n]), paths(new Path[m]) {}
~Net() {
delete[] nodes;
delete[] paths;
}
ui N, M;
Node* nodes;
Path* paths;
void in() {
ui cur = 0;
ui temp;
nodes[0].pos = paths;
for (ui i = 0u; i < M; i++) {
scf("%u%u%u%u", &temp, &paths[i].target, &paths[i].time,
&paths[i].cost);
if (temp == cur)
nodes[cur].len++;
else {
cur = temp;
nodes[cur].pos = &paths[i];
nodes[cur].len = 1;
}
}
for (ui i = 0u; i < N; i++) {
auto* begin = nodes[i].pos;
auto* end = begin + nodes[i].len;
sort(begin, end,
[](Path& a, Path& b) -> bool { return a.cost > b.cost; });
}
}
void adj(stack<Path*>& s, ui node) {
auto* begin = nodes[node].pos;
auto* end = begin + nodes[node].len;
for (auto* i = begin; i < end; i++) s.push(i);
}
void adj(stack<Path*>& s, ui node, bool* vis) {
auto* begin = nodes[node].pos;
auto* end = begin + nodes[node].len;
for (auto* i = begin; i < end; i++)
if (!vis[i->target]) s.push(i);
}
};
ui origin, dest, timeLmt;
struct Result {
ui ret;
bool res;
};
Result dfs1(Net& net) {
struct Status {
ui curTime;
ui curCost;
};
Result result{0, false};
stack<Net::Path*> s;
net.adj(s, origin);
stack<Status> st;
st.push(Status{0, 0});
bool* vis = new bool[net.N]{false};
vis[origin] = true;
while (!s.empty()) {
auto* cur = s.top();
if (vis[cur->target]) {
vis[cur->target] = false;
s.pop();
st.pop();
} else {
Status prevSt = st.top(),
curSt = Status{prevSt.curTime + cur->time};
if (curSt.curTime > timeLmt) {
s.pop();
continue;
}
curSt.curCost = prevSt.curCost + cur->cost;
if (result.res) {
if (curSt.curCost >= result.ret)
s.pop();
else {
if (cur->target == dest) {
result.ret = curSt.curCost;
s.pop();
} else {
vis[cur->target] = true;
st.push(curSt);
net.adj(s, cur->target, vis);
}
}
} else {
if (cur->target == dest) {
result.ret = curSt.curCost;
result.res = true;
s.pop();
} else {
vis[cur->target] = true;
st.push(curSt);
net.adj(s, cur->target, vis);
}
}
}
}
delete[] vis;
return result;
}
Result dfs2(Net& net) {
struct Status {
ui curTime;
ui curCost;
};
Result result{0, false};
stack<Net::Path*> s;
net.adj(s, origin);
stack<Status> st;
st.push(Status{0, 0});
bool* vis = new bool[net.N]{false};
vis[origin] = true;
while (!s.empty()) {
auto* cur = s.top();
if (vis[cur->target]) {
vis[cur->target] = false;
s.pop();
st.pop();
} else {
Status prevSt = st.top(),
curSt = Status{prevSt.curTime + cur->time};
if (curSt.curTime > timeLmt) {
s.pop();
continue;
}
curSt.curCost = prevSt.curCost + cur->cost;
if (result.res) {
if (curSt.curCost >= result.ret)
s.pop();
else {
if (cur->target == dest) {
result.ret = curSt.curCost;
s.pop();
} else {
vis[cur->target] = true;
st.push(curSt);
net.adj(s, cur->target, vis);
}
}
} else {
if (cur->target == dest) {
result.ret = curSt.curCost;
result.res = true;
break;
} else {
vis[cur->target] = true;
st.push(curSt);
net.adj(s, cur->target, vis);
}
}
}
}
delete[] vis;
return result;
}
int main() {
ui N, M;
scf("%u%u", &N, &M);
Net net(N, M);
net.in();
scf("%u%u%u", &origin, &dest, &timeLmt);
auto result = M > 100000 ? dfs2(net) : dfs1(net);
if (result.res)
prf("%u", result.ret);
else
prf("-1");
return 0;
}
时空消耗
1 Accepted 0 ms 912 KB
2 Accepted 0 ms 912 KB
3 Accepted 0 ms 924 KB
4 Accepted 4 ms 960 KB
5 Accepted 0 ms 940 KB
6 Accepted 4 ms 1080 KB
7 Accepted 16 ms 1324 KB
8 Accepted 16 ms 1392 KB
9 Accepted 12 ms 1584 KB
10 Accepted 840 ms 3316 KB