/*
+----------------------------------------------------------------+
| In the name of Allah, the most Gracious and the most Merciful. |
+----------------------------------------------------------------+
+------------------------------------------------------+
| Ба номи Худованди беандоза Mеҳрабон ва ниҳоят Бораҳм |
+------------------------------------------------------+
+-----------------------------------------+
| Во имя Аллаха Милостивого, Милосердного |
+-----------------------------------------+
This world is a trial for us
And we know well that we must
Obey the orders from my lord
To avoid all sins and seek reward
*/
# include <bits/stdc++.h>
# define FILE
using namespace std;
const int N = 3e5 + 100;
const long long inf = 1000000000000000000LL;
int n, m, timm, curr, bridge, U[N], V[N], W[N], maxW[N], tin[N], low[N];
long long dist[2][N], within[N], without[N];
vector < int > graph[N];
void bfs( int v, long long *dist ){
for( int i = 1; i <= n; i ++ ) dist[i] = inf;
dist[v] = 0;
priority_queue < pair <long long, int>, vector<pair<long long, int>>, greater<pair<long long, int> > > pq;
pq.push({0,v});
while( !pq.empty() ){
long long dst; int v; tie(dst, v) = pq.top(); pq.pop();
if( dst > dist[v] )continue;
for( auto i: graph[v] ){
int to = (v == V[i]?U[i]:V[i]);
if( dist[to] > dist[v] + W[i] ){
dist[to] = dist[v] + W[i];
pq.push({dist[to], to});
}
}
}
}
void dfs( int v, int f, int ras ){
tin[v] = low[v] = ++timm;
for( auto i: graph[v] ){
if( without[i] > ras )continue;
int to = (v==V[i]?U[i]:V[i]);
if( tin[to] <= curr ){
dfs(to, v, ras);
if( low[to] > tin[v] && tin[n] >= tin[to] && within[i] > ras )
bridge = 1;
low[v] = min( low[v], low[to]);
}else if( to != f ){
low[v] = min( low[v], tin[to]);
}
}
}
bool check( long long ras){
curr = timm;
bridge = 0;
dfs(1, 0, ras);
//cout << "check " << curr << ' ' << tin[n] << ' ' <<bridge << endl;
if( tin[n] <= curr) return 0;
if( bridge )return 0;
return true;
}
int main(){
# ifdef FILEs
freopen( "input.txt", "r", stdin );
freopen( "output.txt", "w", stdout );
# endif
ios_base::sync_with_stdio(false);
cin >> n >> m;
for( int i = 1; i <= m; i ++ ){
cin >> V[i] >> U[i] >> W[i];
graph[V[i]].push_back( i );
graph[U[i]].push_back( i );
}
for( int i = m-1; i >= 1; i -- ){
maxW[i] = max( W[i+1], maxW[i+1]);
}
bfs( 1, dist[0]);
bfs( n, dist[1]);
for( int i = 1; i <= m; i ++ ){
without[i] = min( dist[0][V[i]] + dist[1][U[i]], dist[0][U[i]] + dist[1][V[i]]) + W[i];
within[i] = without[i] + maxW[i];
}
/*
for( int i = 1; i <= m; i ++ ){
cout << i << ' ' << V[i] <<' ' << U[i] << ' ' << without[i] << ' ' << within[i] <<' ' <<maxW[i]<< endl;
}cout << endl;
*/
long long l = dist[0][n]-1, r = dist[0][n] + maxW[1];
while( r - l > 1 ){
long long mid = ( l + r ) >> 1;
//cout << l << ' '<< mid << ' ' << r << endl;
if( check(mid) )
r = mid;
else
l = mid;
}
cout << r;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
7424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
7424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
7424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
7424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
7424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
7424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
7424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
