| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 261378 | Nightlight | Aesthetic (NOI20_aesthetic) | C++14 | 0 ms | 0 KiB |
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 <cstdio>
#include <queue>
#include <cstring>
#define pii pair<long long, int>
using namespace std;
int N, M;
vector<pii> adj[300005];
priority_queue<pii, vector<pii>, greater<pii>> pq;
long long dist[2][300005];
int U[300005], V[300005];
bitset<300005> can, ada;
long long W[300005], best[300005];
vector<pair<int, int>> adj2[300005];
int disc[300005], low[300005], waktu, need;
long long p1[300005], p2[300005], pp1[300005], pp2[300005];
bool ok;
void BFS(int id, int st) {
memset(ada, 0, sizeof(ada));
pq.emplace(0LL, st);
dist[id][st] = 0;
int u, v;
long long len, w;
while(!pq.empty()) {
u = pq.top().second;
len = pq.top().first;
pq.pop();
if(len != dist[u]) continue;
for(pii now : adj[u]) {
v = now.second;
w = now.first;
if(dist[id][v] > len + w) {
dist[id][v] = len + w;
pq.emplace(dist[id][v], v);
}
}
}
}
void DFS(int u, int p) {
disc[u] = low[u] = ++waktu;
int v, id;
for(pair<int, int> now : adj2[u]) {
id = now.second;
if(ada[id] == 0) continue;
v = now.first;
if(disc[v] <= need) {
DFS(v, u);
if(can[id] && low[v] > disc[u] && disc[N] >= disc[v] && disc[N] <= waktu) {
ok = 1;
}else low[u] = min(low[u], low[v]);
}else if(p != v) {
low[u] = min(low[u], disc[v]);
}
}
}
bool check(long long now) {
ok = 0;
need = waktu;
for(int i = 1; i <= M; i++) {
if(p1[i] > now && p2[i] > now) ada[i] = 0;
else ada[i] = 1;
if(pp1[i] > now && pp2[i] > now) can[i] = 1;
else can[i] = 0;
}
DFS(1, 0);
if(disc[N] <= need) return 1;
if(ok) return 1;
return 0;
}
int main() {
memset(dist, 0x3f3f3f3f, sizeof(dist));
scanf("%d %d", &N, &M);
int u, v;
long long w;
for(int i = 1; i <= M; i++) {
scanf("%d %d %lld", &u, &v, &w);
U[i] = u, V[i] = v, W[i] = w;
adj[u].emplace_back(w, v);
adj[v].emplace_back(w, u);
adj2[u].emplace_back(v, i);
adj2[v].emplace_back(u, i);
}
for(int i = M - 1; i > 0; i--) {
best[i] = max(best[i + 1], W[i + 1]);
}
BFS(0, 1);
BFS(1, N);
for(int i = 1; i <= M; i++) {
p1[i] = dist[0][U[i]] + W[i] + dist[1][V[i]];
p2[i] = dist[0][V[i]] + W[i] + dist[1][U[i]];
pp1[i] = dist[0][U[i]] + best[i] + W[i] + dist[1][V[i]];
pp2[i] = dist[0][V[i]] + best[i] + W[i] + dist[1][U[i]];
}
long long l = dist[0][N], r = dist[0][N] + 1000000000, res = dist[0][N], mid;
while(l <= r) {
mid = (l + r) >> 1;
if(check(mid)) {
l = mid + 1;
res = l;
}else r = mid - 1;
}
printf("%lld\n", res);
}