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>
//#include <quadmath.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#define sz(x) (int)x.size()
//#define sqr(x) x*x
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("no-stack-protector")
//#pragma GCC optimize("fast-math")
using namespace std;
//using namespace __gnu_pbds;
#define int long long
//#define ld long double
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
const int INF = 1e18;
vector<vector<pair<int, int> > > g;
vector<int> es;
vector<int> tin, go;
vector<ll> suff;
vector<bool> used;
vector<ll> d1, dn;
int timer = 0;
bool flag = 0;
void dfs(int v, int p, ll x)
{
used[v] = 1;
tin[v] = go[v] = timer++;
for (auto&[u, ind] : g[v])
{
if (p == u) continue;
if (min(d1[v] + dn[u], d1[u] + dn[v]) + es[ind] >= x) continue;
if (used[u])
{
go[v] = min(go[v], tin[u]);
}
else
{
dfs(u, v, x);
go[v] = min(go[v], go[u]);
if (go[u] > tin[v] && min(d1[v] + dn[u], d1[u] + dn[v]) + es[ind] + suff[ind + 1] >= x)
{
flag = 1;
}
}
}
}
bool f(ll x)
{
flag = 0;
timer = 0;
fill(tin.begin(), tin.end(), 0);
fill(go.begin(), go.end(), INF);
fill(used.begin(), used.end(), 0);
dfs(0, -1, x);
return flag || tin.back() == 0;
}
void dijkstra(int s, vector<ll>& dist)
{
fill(dist.begin(), dist.end(), 1e18);
set<pair<ll, int> > st;
st.insert({0, s});
dist[s] = 0;
while (!st.empty())
{
auto [d, v] = *st.begin();
st.erase(st.begin());
for (auto&[u, ind] : g[v])
{
ll w = es[ind];
if (dist[u] > dist[v] + w)
{
st.erase({dist[u], u});
dist[u] = dist[v] + w;
st.insert({dist[u], u});
}
}
}
}
void solve()
{
int n, m;
cin >> n >> m;
es.resize(m);
suff.resize(m + 1);
g.resize(n);
tin.resize(n);
d1.resize(n);
dn.resize(n);
go.resize(n);
used.resize(n);
for (int i = 0; i < m; i++)
{
int x, y, z;
cin >> x >> y >> z;
x--; y--;
g[x].push_back({y, i});
g[y].push_back({x, i});
es[i] = z;
}
suff[m - 1] = es[m - 1];
for (int i = m - 2; i >= 0; i--)
{
suff[i] = max(suff[i + 1], es[i]);
}
dijkstra(0, d1);
dijkstra(n - 1, dn);
ll lt = d1[n - 1], rt = d1[n - 1] + suff[0] + 1;
while (rt - lt > 1)
{
ll mid = (lt + rt) >> 1;
if (f(mid))
{
lt = mid;
}
else
{
rt = mid;
}
}
cout << lt;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
t = 1;
while (t--)
{
solve();
}
return 0;
}
/*
4 4
1 2 1 3
1 1
1 2
1 3
1 4
*/
# | 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... |