QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#273161 | #7883. Takeout Delivering | ucup-team133# | Compile Error | / | / | C++23 | 3.4kb | 2023-12-02 21:43:14 | 2023-12-02 21:43:15 |
Judging History
你现在查看的是最新测评结果
- [2023-12-06 22:45:03]
- hack成功,自动添加数据
- (//qoj.ac/hack/491)
- [2023-12-02 21:43:15]
- 评测
- 测评结果:Compile Error
- 用时:0ms
- 内存:0kb
- [2023-12-02 21:43:14]
- 提交
answer
#include <bits/stdc++.h>
#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...) void(0)
#endif
#include "datastructure/UnionFind.hpp"
using namespace std;
typedef long long ll;
#define all(x) begin(x), end(x)
constexpr int INF = (1 << 30) - 1;
constexpr long long IINF = (1LL << 60) - 1;
constexpr int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
template <class T> istream& operator>>(istream& is, vector<T>& v) {
for (auto& x : v) is >> x;
return is;
}
template <class T> ostream& operator<<(ostream& os, const vector<T>& v) {
auto sep = "";
for (const auto& x : v) os << exchange(sep, " ") << x;
return os;
}
template <class T, class U = T> bool chmin(T& x, U&& y) { return y < x and (x = forward<U>(y), true); }
template <class T, class U = T> bool chmax(T& x, U&& y) { return x < y and (x = forward<U>(y), true); }
template <class T> void mkuni(vector<T>& v) {
sort(begin(v), end(v));
v.erase(unique(begin(v), end(v)), end(v));
}
template <class T> int lwb(const vector<T>& v, const T& x) { return lower_bound(begin(v), end(v), x) - begin(v); }
struct edge {
int u, v, w;
edge(int u, int v, int w) : u(u), v(v), w(w) {}
bool operator<(const edge& rhs) const { return w < rhs.w; }
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<edge> es;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
es.emplace_back(--u, --v, w);
}
sort(begin(es), end(es));
UnionFind UF(n);
int border = -1, threshold = -1;
vector<vector<pair<int, int>>> G(n);
for (int i = 0; i < m; i++) {
auto [u, v, w] = es[i];
UF.merge(u, v);
G[u].emplace_back(v, w);
G[v].emplace_back(u, w);
if (UF.same(0, n - 1)) {
border = i + 1;
threshold = w;
break;
}
}
assert(border != -1);
ll ans = IINF;
{
vector dp(n, vector<int>(2, INF));
priority_queue<tuple<int, int, int>> pq;
dp[0][0] = 0;
pq.emplace(-dp[0][0], 0, 0);
while (not pq.empty()) {
auto [cost, v, x] = pq.top();
pq.pop();
cost *= -1;
if (dp[v][x] != cost) continue;
for (auto [u, w] : G[v]) {
int nx = x, ncost = cost;
if (x == 0 and w == threshold) {
nx++;
} else
chmax(cost, w);
if (chmin(dp[u][nx], ncost)) pq.emplace(-dp[u][nx], u, nx);
}
}
ans = dp[n - 1][1] + threshold;
}
{
auto calc = [&](int s) -> vector<int> {
vector<int> dp(n, INF);
priority_queue<pair<int, int>> pq;
dp[s] = 0;
pq.emplace(-dp[s], s);
while (not pq.empty()) {
auto [cost, v] = pq.top();
pq.pop();
cost *= -1;
if (dp[v] != cost) continue;
for (auto [u, w] : G[v]) {
if (chmin(dp[u], max(cost, w))) pq.emplace(-dp[u], u);
}
}
return dp;
};
auto dp1 = calc(0), dp2 = calc(n - 1);
for (int i = border; i < m; i++) {
auto [u, v, w] = es[i];
if (dp1[u] == INF) continue;
if (dp2[v] == INF) continue;
chmin(ans, w + max(dp1[u], dp2[v]));
}
}
cout << ans << '\n';
return 0;
}
詳細信息
answer.code:8:10: fatal error: datastructure/UnionFind.hpp: No such file or directory 8 | #include "datastructure/UnionFind.hpp" | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~ compilation terminated.