This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//Nov21-2020
#define tasknames "aesthetic"
#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
const int maxn=3e5+2;
int n, m, x[maxn], y[maxn], c[maxn], maxc[maxn], Time=0, num[maxn], low[maxn];
long long d[2][maxn];
bool ch[2][maxn], kt;
stack<int> st;
struct T
{
int v, w, id;
};
vector<T> a[maxn];
void Dijkstra(int s,int h)
{
priority_queue<pair<long long,int>> pq;
for(int i=1;i<=n;i++)
d[h][i]=1e18;
d[h][s]=0;
pq.push({0,s});
while(!pq.empty())
{
auto u=pq.top();
pq.pop();
u.first=-u.first;
if(u.first!=d[h][u.second])
continue;
for(T v:a[u.second])
if(d[h][v.v]>u.first+v.w)
{
d[h][v.v]=u.first+v.w;
pq.push({-d[h][v.v],v.v});
}
}
}
void Enter()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int u, v, w;
cin>>u>>v>>w;
a[u].push_back({v,w,i});
a[v].push_back({u,w,i});
x[i]=u;y[i]=v;c[i]=w;
}
for(int i=m;i>0;i--)
maxc[i]=max(maxc[i+1],c[i+1]);
Dijkstra(1,0);
Dijkstra(n,1);
}
void Tarjan(int u,int par)
{
num[u]=low[u]=++Time;
for(T v:a[u])
{
if(!ch[0][v.id])continue;
if(num[v.v])
{
if(v.v!=par)
low[u]=min(low[u],num[v.v]);
}
else
{
Tarjan(v.v,u);
if(low[v.v]>num[u]&&num[n]>=num[v.v]&&ch[1][v.id])
kt=true;
else low[u]=min(low[u],low[v.v]);
}
}
}
bool Check(long long mid)
{
for(int i=1;i<=m;i++)
{
long long dist=min(d[0][x[i]]+d[1][y[i]],d[1][x[i]]+d[0][y[i]])+c[i];
ch[0][i]=(dist<=mid);
ch[1][i]=((dist+maxc[i])>mid);
}
fill_n(num,n+1,0);
fill_n(low,n+1,1e9);
Time=0;kt=false;
Tarjan(1,0);
if(kt||num[n]==0)return true;
return false;
}
void Solve()
{
long long l=d[0][n], r=d[0][n]+maxc[1], mid;
while(l<=r)
{
mid=(l+r)/2;
if(Check(mid))
l=mid+1;
else r=mid-1;
}
cout<<l;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
Enter();
Solve();
}
# | 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... |