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>
#define err(args...) {}
#ifdef DEBUG
#include "_debug.cpp"
#endif
using namespace std;
using ll = long long;
using ld = long double;
template <typename T> using lim = numeric_limits<T>;
template <typename T> istream& operator>>(istream& is, vector<T>& a) { for(T& x : a) { is >> x; } return is; }
template <typename X, typename Y> istream& operator>>(istream& is, pair<X, Y>& p) { return is >> p.first >> p.second; }
template <typename T> struct wedge {
int i, u, v; T w, dw;
wedge reverse() const { return {i, v, u, w, dw}; }
friend ostream& operator<<(ostream& os, const wedge& e) {
return os << "{u: " << e.u << ", v: " << e.v << ", w: " << e.w << "}";
}
};
template <bool Directed, typename TEdge, bool Index> struct graph {
using EType = TEdge;
vector<TEdge> edges;
vector<vector<int>> adj;
graph(int n) : adj(n + Index) {}
graph(int n, int m) : graph(n) { edges.reserve(m << not Directed); }
TEdge& operator()(int e) { return edges[e]; }
vector<int>& operator[](int u) { return adj[u]; }
int size() { return adj.size() - Index; }
void append(int u, const TEdge& e) {
adj[u].push_back(edges.size());
edges.push_back(e);
}
void add_edge(const TEdge& e) {
append(e.u, e);
if(not Directed) append(e.v, e.reverse());
}
};
template <bool Directed, typename T, bool Index>
pair<vector<T>, vector<int>> sssp(graph<Directed, wedge<T>, Index>& g, const vector<int>& s) {
vector<int> vis(g.adj.size()), p(g.adj.size(), -1);
vector<T> d(g.adj.size(), lim<T>::max());
priority_queue<pair<T, int>> pq;
for(int u : s) {
pq.push({d[u] = 0, u});
}
while(not pq.empty()) {
int u = pq.top().second; pq.pop();
if(not vis[u]) {
vis[u] = true;
for(int e : g[u]) {
if(not vis[g(e).v] and d[g(e).v] > d[u] + g(e).w) {
pq.push({-(d[g(e).v] = d[u] + g(e).w), g(p[g(e).v] = e).v});
}
}
}
}
return {move(d), move(p)};
}
template <bool Directed, typename TEdge, bool Index>
vector<int> construct_path(graph<Directed, TEdge, Index>& g, const vector<int>& parent, int t) {
vector<int> ans = {t};
while(parent[ans.back()] != -1) {
ans.push_back(g(parent[ans.back()]).u);
}
reverse(ans.begin(), ans.end());
return ans;
}
template <typename TEdge, bool Index> pair<vector<int>, vector<vector<int>>> find_2eccs(graph<0, TEdge, Index>& g) {
vector<int> vis(g.adj.size()), low(g.adj.size()), cut_edge(g.edges.size()), s;
vector<vector<int>> _2eccs = {};
int timer = 1;
function<void(int, int)> dfs = [&](int u, int from) {
vis[u] = low[u] = timer++;
s.push_back(u);
for(int e : g[u]) {
if(not vis[g(e).v]) {
dfs(g(e).v, e & ~1);
if(vis[u] < low[g(e).v]) {
cut_edge[e] = cut_edge[e ^ 1] = true;
_2eccs.push_back(vector<int>());
do {
_2eccs.back().push_back(s.back()), s.pop_back();
} while(_2eccs.back().back() != g(e).v);
}
low[u] = min(low[u], low[g(e).v]);
} else if((e & ~1) != from and vis[u] > vis[g(e).v]) {
low[u] = min(low[u], vis[g(e).v]);
}
}
};
for(int u = Index; u < g.adj.size(); u++) if(not vis[u]) {
dfs(u, -1);
_2eccs.push_back(vector<int>());
while(not s.empty()) {
_2eccs.back().push_back(s.back()), s.pop_back();
}
}
return {move(cut_edge), move(_2eccs)};
}
const int MAX_WI = 10;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
graph<0, wedge<ll>, 1> g(n, m);
for(int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
g.add_edge({i, u, v, w});
}
ll max_dw = 0;
for(int i = m - 1; i >= 0; i--) {
g.edges[2 * i].dw = g.edges[2 * i + 1].dw = max_dw;
max_dw = max(max_dw, g.edges[2 * i].w);
}
auto [ds, ps] = sssp(g, {1});
auto [dt, pt] = sssp(g, {n});
ll ans = ds[n];
for(int delta = 1; delta <= MAX_WI; delta++) {
graph<0, wedge<ll>, 1> sp_dag(n);
for(int ii = 0; ii < g.edges.size(); ii += 2) {
auto [i, u, v, w, dw] = g.edges[ii];
ll uv_path = ds[u] + w + dt[v];
ll vu_path = ds[v] + w + dt[u];
if(min(uv_path, vu_path) < ds[n] + delta) {
if(min(uv_path, vu_path) == uv_path) {
sp_dag.add_edge({i, u, v, w, dw});
} else {
sp_dag.add_edge({i, v, u, w, dw});
}
}
}
auto [d, p] = sssp(sp_dag, {1});
auto path = construct_path(sp_dag, p, n);
set<pair<int, int>> on_path;
for(int i = 1; i < path.size(); i++) {
on_path.insert({path[i - 1], path[i]});
}
auto [cut_edge, _2eccs] = find_2eccs(sp_dag);
bool increase = false;
for(int ii = 0; ii < sp_dag.edges.size(); ii += 2) {
auto [i, u, v, w, dw] = sp_dag.edges[ii];
increase |= cut_edge[ii] and on_path.count({u, v}) and ds[u] + w + dw + dt[v] >= ds[n] + delta;
}
if(increase) {
ans = ds[n] + delta;
}
}
cout << ans << endl;
return 0;
}
Compilation message (stderr)
Aesthetic.cpp: In function 'int main()':
Aesthetic.cpp:121:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<wedge<long long int>, std::allocator<wedge<long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | for(int ii = 0; ii < g.edges.size(); ii += 2) {
| ~~~^~~~~~~~~~~~~~~~
Aesthetic.cpp:136:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
136 | for(int i = 1; i < path.size(); i++) {
| ~~^~~~~~~~~~~~~
Aesthetic.cpp:141:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<wedge<long long int>, std::allocator<wedge<long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
141 | for(int ii = 0; ii < sp_dag.edges.size(); ii += 2) {
| ~~~^~~~~~~~~~~~~~~~~~~~~
Aesthetic.cpp: In instantiation of 'std::pair<std::vector<int>, std::vector<std::vector<int> > > find_2eccs(graph<false, TEdge, Index>&) [with TEdge = wedge<long long int>; bool Index = true]':
Aesthetic.cpp:139:52: required from here
Aesthetic.cpp:90:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for(int u = Index; u < g.adj.size(); u++) if(not vis[u]) {
| ~~^~~~~~~~~~~~~~
# | 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... |