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;
typedef long long ll;
typedef pair<ll, ll> pii;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N = (int)3e5 + 10;
int u[N], v[N], w[N];
int p[N];
vector<pii> T[N];
ll dist[2][N];
bool has[N];
int n,m,c;
void dijik(int x){
priority_queue<pii,vector<pii>,greater<pii>> gg;
int node;
for(int i = 1; i <= n; i ++ ){
dist[c][i]=(ll)1e14;
has[i]=false;
}
dist[c][x]=0ll;
gg.push(mp(0,x));
while(!gg.empty()){
node = gg.top().se;
gg.pop();
if(has[node]) continue;
has[node]=true;
for(auto x : T[node]){
if(dist[c][node] + w[x.se] < dist[c][x.fi]){
dist[c][x.fi] = dist[c][node] + w[x.se];
gg.push(mp(dist[c][x.fi], x.fi));
}
}
}
c++;
}
vector<pii> E[N];
int tin[N];
int low[N];
ll attm;
int tt;
bool bridge[N];
void dfs(int u, int par){
tin[u] = ++tt;
low[u] = tin[u];
for(auto x : E[u]){
if(x.fi == par) continue;
if(tin[x.fi] != -1){
low[u] = min(low[u], tin[x.fi]);
}
else{
dfs(x.fi, u);
low[u] = min(low[u], low[x.fi]);
if(tin[u] < low[x.fi]){
bridge[x.se] = true;
}
}
}
}
int ids[N];
int id;
void dfs1(int u, int par){
ids[u]=id;
for(auto x : E[u]){
if(ids[x.fi] != -1) continue;
if(bridge[x.se]) continue;
dfs1(x.fi, u);
}
}
bool bad;
int pid[N];
int ip[N];
bool vis[N];
void dfs2(int u, int par){
vis[u]=true;
for(auto x : E[u]){
if(vis[x.fi]) continue;
if(bridge[x.se]){
pid[ids[x.fi]] = ids[u];
ip[ids[x.fi]] = x.se;
dfs2(x.fi, u);
}
else{
dfs2(x.fi, u);
}
}
}
bool check(ll dis){
attm = dis;
tt = 0;
for(int i = 0 ; i < m ; i ++ ){
bridge[i]=false;
}
for(int i = 1; i <= n; i ++ ){
E[i].clear();
vis[i]=false;
tin[i] = -1, low[i] = -1;
ids[i] = -1;
pid[i] = -1;
ip[i] = -1;
}
id = 0;
for(int i = 0 ; i < m ; i ++ ){
if(dist[0][u[i]] + w[i] + dist[1][v[i]] <= dis || dist[0][v[i]] + w[i] + dist[1][u[i]] <= dis){
E[u[i]].push_back(mp(v[i], i));
E[v[i]].push_back(mp(u[i], i));
}
}
dfs(1, 0);
if(tin[n] == -1) return false; // we assume it is reachable at this point
bad = false;
for(int i = 1; i <= n; i ++ ){
if(tin[i] != -1 && ids[i] == -1){
id ++ ;
dfs1(i,-1);
}
}
dfs2(1, 0);
int node = ids[n];
int ed;
while(node != ids[1]){
ed = ip[node];
node = pid[node];
if(dist[0][u[ed]] + dist[1][v[ed]] + w[ed] + p[ed+1] > dis && dist[1][u[ed]] + dist[0][v[ed]] + w[ed] + p[ed+1] > dis)
return false;
}
return true;
}
int main(){
fastIO;
cin >> n >> m;
for(int i = 0 ; i < m ; i ++ ){
cin >> u[i] >> v[i] >> w[i];
T[u[i]].push_back(mp(v[i],i));
T[v[i]].push_back(mp(u[i],i));
}
dijik(1);
dijik(n);
for(int i = m-1; i >= 0 ; i -- ){
p[i]=w[i];
p[i]=max(p[i],p[i+1]);
}
ll li = dist[0][n], ri = li+p[1];
ll mid;
while(li < ri){
mid = (li + ri) / 2;
if(check(mid))
ri = mid;
else
li = mid + 1;
}
cout << li << "\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... |