#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
const int maxn = 300010;
int n,e;
vector <pi> adjlist[maxn];
int A[maxn], B[maxn], cost[maxn];
int worst[maxn];
int dist[2][maxn]; //node 1 to any node, and node n to any node
void precalc(int start, int type) {
memset(dist[type],-1,sizeof dist[type]);
dist[type][start] = 0;
priority_queue<pi,vector<pi>,greater<pi>> pq;
pq.push(pi(0,start));
while (!pq.empty()) {
pi cur = pq.top(); pq.pop();
int d = cur.f, x = cur.s;
if (dist[type][x] != d) continue;
for (auto i: adjlist[x]) {
if (dist[type][i.f] == -1 or dist[type][i.f] > d + cost[i.s]) {
dist[type][i.f] = d + cost[i.s];
pq.push(pi(dist[type][i.f],i.f));
}
}
}
}
int insmallpath[maxn];
int isbridge[maxn],canboost[maxn];
bool vis[maxn];
bool works;
int co;
int timev[maxn], lowv[maxn];
void findbridges(int x, int p) {
timev[x] = lowv[x] = co++;
for (auto cure: adjlist[x]) {
int i = cure.f, index = cure.s;
if (insmallpath[index] == 0) continue;
if (i == p) continue;
if (timev[i] != -1) {
lowv[x] = min(lowv[x], lowv[i]);
} else {
findbridges(i,x);
lowv[x] = min(lowv[x], lowv[i]);
if (lowv[i] >= timev[x]) {
//cout << "BRIDGE: " << index << " " << A[index] << " " << B[index] << " " << canboost[index] << "\n";
if (canboost[index]) isbridge[index] = true;
}
}
}
}
void dfs(int x, int p) {
vis[x] = 1;
if (x == n) {
works = false;
return;
}
for (auto i: adjlist[x]) {
if (i.f == p) continue;
if (isbridge[i.s] == 1 or insmallpath[i.s] == 0) continue;
if (vis[i.f]) continue;
dfs(i.f,x);
}
}
bool test(int L) { //Returns true if we can make the shortest path more than L.
for (int i =0;i<e;i++) {
if (dist[0][A[i]] + cost[i] + dist[1][B[i]] <= L) insmallpath[i] = 1;
else if (dist[1][A[i]] + cost[i] + dist[0][B[i]] <= L) insmallpath[i] = 1;
else insmallpath[i] = 0;
}
//for (int i =0;i<e;i++) {
//cout << A[i] << " " << B[i] << " " << insmallpath[i] << "\n";
//}
for (int i =0;i<e;i++) {
if (dist[0][A[i]] + cost[i] + worst[i] + dist[1][B[i]] > L and dist[1][A[i]] + cost[i] + worst[i] + dist[0][B[i]] > L) canboost[i] = 1;
else canboost[i] = 0;
}
co = 0;
memset(timev,-1,sizeof timev);
memset(lowv, 0,sizeof lowv);
memset(isbridge,0,sizeof isbridge);
findbridges(1,-1);
memset(vis,0,sizeof vis);
works = true;
dfs(1,-1);
if (works) return true;
else return false;
}
int32_t main() {
FAST
cin >> n >> e;
for (int i =0;i<e;i++) {
cin >> A[i] >> B[i] >> cost[i];
adjlist[A[i]].push_back(pi(B[i],i));
adjlist[B[i]].push_back(pi(A[i],i));
}
for (int i =e-1;i>=0;i--) {
worst[i] = max(worst[i+1], cost[i+1]);
}
precalc(1,0);
precalc(n,0);
int high = 1e9;
int low = dist[0][n];
while (high - low > 1) {
int mid = (high+low)/2;
//cout << "NEW: " << mid << " " << low << " " << high << "\n";
if (test(mid)) low = mid;
else high = mid;
}
cout << high;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
17152 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
17152 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
754 ms |
46968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
671 ms |
47736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2100 ms |
53460 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2100 ms |
53460 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
17152 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
