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 int long long
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define ll long long
#define pb push_back
#define vi vector<int>
#define se second
#define fi first
using namespace std;
const int N = 3e5+5;
vector<pii> adj[N];
int n,m;
int A[N],B[N],W[N],NUM[N][2],MX[N],par[N],good[N],sub[N],id[N];
ll D[N],FROM_N[N],H[N];
set<pii> path;
ll t[4*N];
void upd(int v,int tl,int tr,int l,int r,ll val) {
if(l > tr || r < tl) return;
if (l <= tl && r >= tr) {
t[v] = val;
return;
}
t[v*2] = min(t[v*2],t[v]);
t[v*2+1] = min(t[v*2+1],t[v]);
int tm = (tl + tr)/2;
upd(v*2,tl,tm,l,r,val);
upd(v*2+1,tm+1,tr,l,r,val);
//t[v] = min(t[v*2],t[v*2+1]);
}
void down(int v,int tl,int tr) {
if (tl == tr) H[tl] = t[v];
else {
int tm = (tl + tr)/2;
t[v*2] = min(t[v*2],t[v]);
t[v*2+1] = min(t[v*2+1],t[v]);
down(v*2,tl,tm);
down(v*2+1,tm+1,tr);
}
}
void dijkstra(int s) {
priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > > pq;
pq.push({0,s});
vector<bool> vis(n+1);
vector<ll> d(n+1);
for (int i = 1; i <= n; i++)
d[i] = 10000000000000000;
d[s] = 0;
par[s] = 0;
id[s] = 0;
while(!pq.empty()) {
auto i1 = pq.top();
pq.pop();
int v = i1.se;
if (vis[v]) continue;
ll dis = i1.fi;
vis[v] = 1;
for (auto i : adj[v])
if (!vis[i.fi] && d[i.fi] > dis + i.se) {
d[i.fi] = dis + i.se;
id[i.fi] = id[v] + 1;
par[i.fi] = v;
pq.push({d[i.fi],i.fi});
}
}/*1 2 3
2 3 5
1 3 4*/
if (s == n)
for (int i = 1; i <= n; i++)
FROM_N[i] = d[i];
else {
for (int i = 1; i <= n; i++)
D[i] = d[i];
int j = n;
good[1] = 1;
while(j != 1) {
good[j] = 1;
j = par[j];
}
for (int i = 2; i <= n; i++) {
if (good[i])
path.insert({i,par[i]}),
path.insert({par[i],i});
}
vector<pair<ll,int> > g;
for (int i =1 ; i <= n; i++) {
g.pb({d[i],i});
}
sort(all(g));
for (auto i1 : g) {
int v = i1.se;
if (!good[v])
sub[v] = sub [ par[v] ];
else sub[v] = v;
}
}
}
main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a,b,w;
cin >> a >> b >> w;
A[i] = a, B[i] = b;
W[i] = w;
NUM[i][0] = adj[a].size();
NUM[i][1] = adj[b].size();
adj[a].pb({b,w});
adj[b].pb({a,w});
MX[i] = w;
}
dijkstra(n);
dijkstra(1);
for (int i = 1; i < 4*N; i++)
t[i] = 10000000000000000;
// cout << FROM_N[1];exit(0);
for (int i = m-2; i >= 0; i--)
MX[i] = max(MX[i],MX[i+1]);
ll ans = D[n];
// cout << D[n];exit(0);
/*for (int i = 0; i < m; i++) {
int a = A[i], b = B[i];
adj[a][NUM[i][0]].se += MX[i+1];
adj[b][NUM[i][1]].se += MX[i+1];
// dijkstra
priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > > pq;
pq.push({0,1});
vector<bool> vis(n+1);
vector<ll> d(n+1);
for (int i = 1; i <= n; i++)
d[i] = 10000000000000000;
d[1] = 0;
while(!pq.empty()) {
auto i1 = pq.top();
pq.pop();
int v = i1.se;
if (vis[v]) continue;
ll dis = i1.fi;
if (v == n) {
ans = max(ans,dis);
break;
}
vis[v] = 1;
for (auto i : adj[v])
if (!vis[i.fi] && d[i.fi] > dis + i.se) {
d[i.fi] = dis + i.se;
pq.push({d[i.fi],i.fi});
}
}
// replace
adj[a][NUM[i][0]].se -= MX[i+1];
adj[b][NUM[i][1]].se -= MX[i+1];
}*/
vector<pair<ll,pii> > q;
for (int i = 0; i < m; i++) {
int a = A[i], b = B[i];
if (path.count({a,b}) || sub[a] == sub[b]) continue;
if (id[sub[a]] > id[sub[b]]) swap(a,b);
ll dis = D[a] + FROM_N[b] + W[i];
a = sub[a];
b = sub[b];
if (id[a] > id[b]) swap(a,b);
// if (id[sub])
q.pb({dis,{id[a],id[b]-1}});
// upd(1,0,id[n],id[a],id[b]-1,dis);
}
sort(q.rbegin(),q.rend());
for (auto i1 : q) {
int a = i1.se.fi;
int b = i1.se.se;
ll val = i1.fi;
upd(1,0,id[n],a,b,val);
}
down(1,0,id[n]);
for (int i = 0; i < m; i++) {
int a = A[i], b = B[i];
if (path.count({a,b}) == 0) continue;
if (id[a] > id[b]) swap(a,b);
if (H[id[a]] != 10000000000000000)
ans = max(ans, min(H[id[a]],D[n] + MX[i+1]));
else ans = max(ans,D[n] + MX[i+1]);
/* ll C = D[n];
C += MX[i+1];
//adj[a][NUM[i][0]].se += MX[i+1];
//adj[b][NUM[i][1]].se += MX[i+1];
// dijkstra
for (int i = 0; i < m; i++) {
int x = A[i], y = B[i];
if (id[sub[x]] > id[sub[y]]) swap(x,y);
if (x == a && y == b ) continue;
if (id[sub[x]] > id[a] || id[sub[y]] < id[b]) continue;
C = min(C,D[x] + FROM_N[y] + W[i]);
}
ans = max(ans,C);
*/
}
// replace
//adj[a][NUM[i][0]].se -= MX[i+1];
//adj[b][NUM[i][1]].se -= MX[i+1];
cout << ans;
}
Compilation message (stderr)
Aesthetic.cpp:99:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
99 | main() {
| ^
# | 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... |