This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll,ll>;
constexpr ll inf = 1e12 + 7;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
// Custom hash function for pairs of long long
struct pair_hash {
template <class T1, class T2>
std::size_t operator () (const std::pair<T1, T2> &pair) const {
auto hash1 = std::hash<T1>{}(pair.first);
auto hash2 = std::hash<T2>{}(pair.second);
return hash1 ^ hash2;
}
};
// Define hash table with custom hash function
template <class K, class V>
using ht = gp_hash_table<
K, V, pair_hash, equal_to<K>, direct_mask_range_hashing<>, linear_probe_fn<>,
hash_standard_resize_policy<hash_exponential_size_policy<>,
hash_load_check_resize_trigger<>, true>>;
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
ll n, m; cin >> n >> m;
vector<vector<tuple<ll,ll,ll>>> f(n + 1);
for (ll i = 0; i < m; ++i) {
ll a, b, c, d; cin >> a >> b >> c >> d;
f[a].emplace_back(c,b,d);
f[b].emplace_back(c,a,d);
}
vector<vector<tuple<ll,ll,ll>>> g(n + 1);
for (ll i = 1; i <= n; ++i) {
for (auto [c, node, d] : f[i]) {
g[i].emplace_back(node,d,c);
}
}
priority_queue<tuple<ll,ll,ll>,vector<tuple<ll,ll,ll>>,greater<>> pq;
pq.emplace(0,1,0);
vector<ll> d(n + 1,inf);
ht<pair<long long, long long>, int> visited;
while (!pq.empty()) {
auto [cost, cur, par] = pq.top();pq.pop();
if (visited[{cur,par}]) continue;
d[cur] = min(d[cur],cost);
visited[{cur,par}] = true;
map<ll, ll> app;
for (auto [child,len, c] : g[cur]) {
if (child == par) continue;
app[c] += len;
}
for (auto [child, len, c] : g[cur]) {
if (child == par) continue;
if (visited[{child,cur}]) continue;
pq.emplace(cost + len,child,cur);
pq.emplace(cost + app[c] - len,child,-cur);
}
}
if (d[n] == inf) {
cout << "-1";
return 0;
}
cout << d[n];
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |