#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#warning change mxn
const int mxn = 3e3+5;
const ll inf = 1e16;
struct Edge {
int to, id;
};
int n, m;
int A[mxn], B[mxn];
vector<Edge> adj[mxn];
ll W[mxn];
vector<Edge> adj2[mxn];
bool isbridge[mxn], visited[mxn];
vector<ll> from1, fromn;
vector<ll> get_min_dist(int start) {
vector<long long> dist(n+1, inf);
priority_queue<pair<ll, int>> pq;
dist[start] = 0;
pq.push({-dist[start], start});;
while(!pq.empty()) {
ll d = -pq.top().first;
int a = pq.top().second;
pq.pop();
if(dist[a] != d) continue;
for(auto e : adj[a]) if(dist[e.to] > d+W[e.id]) {
dist[e.to] = d+W[e.id];
pq.push({-dist[e.to], e.to});
}
}
return dist;
}
int tim = 0;
int disc[mxn], low[mxn];
bool onpathton[mxn];
void bridge_det(int u, int par) {
visited[u] = true;
if(u == n) onpathton[u] = true;
low[u] = disc[u] = tim++;
for(auto e : adj2[u]) if(e.to != par) {
if(!visited[e.to]) {
bridge_det(e.to, u);
if(low[e.to] > disc[u] && onpathton[e.to]) {
isbridge[e.id] = true;
}
}
onpathton[u] = onpathton[u] || onpathton[e.to];
low[u] = min(low[u], low[e.to]);
}
}
int main(int argc, char const *argv[]) {
cin >> n >> m;
for(int i = 1; i <= m; i++) {
cin >> A[i] >> B[i] >> W[i];
adj[A[i]].push_back({B[i], i});
adj[B[i]].push_back({A[i], i});
}
from1 = get_min_dist(1);
fromn = get_min_dist(n);
ll mxw = W[m];
vector<ll> ans(m+1);
for(int i = m-1; i >= 1; i--) {
ll nw = W[i]+mxw;
ll mndist = inf;
mndist = min(mndist, from1[A[i]]+fromn[B[i]]+nw);
mndist = min(mndist, from1[B[i]]+fromn[A[i]]+nw);
ans[i] = mndist;
mxw = max(mxw, W[i]);
}
// build new graph where every path is min
for(int i = 1; i <= m; i++) {
if(from1[A[i]]+fromn[B[i]]+W[i] == from1[n] || from1[B[i]]+fromn[A[i]]+W[i] == from1[n]) {
adj2[A[i]].push_back({B[i], i});
adj2[B[i]].push_back({A[i], i});
}
}
// printf("new graph\n");
// for(int i = 1; i <= n; i++) {
// printf("%d: ", i);
// for(auto e : adj2[i]) {
// printf("%d (%d), ", e.to, e.id);
// }
// printf("\n");
// }
fill(low, low+n+1, mxn);
bridge_det(1, -1);
// printf("bridges: ");
// for(int i = m; i >= 1; i--) if(isbridge[i]) printf("%d ", i);
// printf("\n");
vector<int> cnt_to_id(m+1);
fill(visited, visited+n+1, false);
queue<int> q;
visited[1] = true; q.push(1);
int c = 0;
while(!q.empty()) {
int u = q.front(); q.pop();
for(auto e : adj2[u]) if(!visited[e.to]) {
visited[e.to] = true;
c += isbridge[e.id];
if(isbridge[e.id]) cnt_to_id[c] = e.id;
q.push(e.to);
}
}
vector<long long> dist(n+1, inf);
vector<int> cnt(n+1);
priority_queue<pair<pair<ll, int>, int>> pq;
vector<Edge> used_edge; vector<int> from;
dist[1] = 0, cnt[1] = 0;
pq.push({{-dist[1], 1}, -1});
vector<vector<ll>> ins(m+1), del(m+1);
while(!pq.empty()) {
ll d = -pq.top().first.first;
int a = pq.top().first.second;
int edgeidx = pq.top().second;
pq.pop();
if(edgeidx != -1) {
// cerr << from[edgeidx] << " -> " << a << "\n";
// cerr << cnt[from[edgeidx]]+isbridge[used_edge[edgeidx].id] << "; " << cnt[a] << "\n";
if(cnt[used_edge[edgeidx].to] > cnt[from[edgeidx]]+isbridge[used_edge[edgeidx].id]) {
int l = cnt[from[edgeidx]]+isbridge[used_edge[edgeidx].id]+1, r = cnt[a];
ll val = from1[from[edgeidx]]+W[used_edge[edgeidx].id]+fromn[a];
// for(int i = l; i <= r; i++) {
// // cerr << "modify " << cnt_to_id[i] << "\n";
// ans[cnt_to_id[i]] = min(ans[cnt_to_id[i]], val);
// }
// cerr << l << "; " << r << ": " << val << "\n";
ins[l].push_back(val);
del[r].push_back(val);
}
}
if(dist[a] != d) continue;
// cerr << a << " " << d << "\n";
for(auto e : adj[a]) {
if(dist[e.to] > d+W[e.id]) {
cnt[e.to] = cnt[a]+isbridge[e.id];
dist[e.to] = d+W[e.id];
pq.push({{-dist[e.to], e.to}, used_edge.size()});
used_edge.push_back(e); from.push_back(a);
// cerr << "add " << from.back() << " " << used_edge.back().to << "\n";
}
else {
// cerr << a << " -> " << e.to << "\n";
// cerr << cnt[a]+isbridge[e.id] << "; " << cnt[e.to] << "\n";
if(cnt[e.to] > cnt[a]+isbridge[e.id]) {
int l = cnt[a]+isbridge[e.id]+1, r = cnt[e.to];
ll val = from1[a]+W[e.id]+fromn[e.to];
// for(int i = l; i <= r; i++) {
// // cerr << i << ": " << cnt_to_id[i] << "?\n";
// ans[cnt_to_id[i]] = min(ans[cnt_to_id[i]], val);
// }
// cerr << l << "; " << r << ": " << val << "\n";
ins[l].push_back(val);
del[r].push_back(val);
}
}
}
}
multiset<ll> available;
for(int i = 0; i <= m; i++) {
for(ll x : ins[i]) available.insert(x);
if(cnt_to_id[i] != 0 && !available.empty()) {
// cerr << cnt_to_id[i] << " <- " << (*available.begin()) << "\n";
ans[cnt_to_id[i]] = min(ans[cnt_to_id[i]], *available.begin());
}
for(ll x : del[i]) available.erase(available.find(x));
}
ll answer = 0;
for(int i = 1; i < m; i++) {
// cerr << ans[i] << "/" << from1[n] << " (" << (isbridge[i] ? ans[i] : from1[n]) << ") ";
answer = max(answer, isbridge[i] ? ans[i] : from1[n]);
}
// cerr << "\n";
cout << answer << "\n";
return 0;
}
Compilation message
Aesthetic.cpp:7:2: warning: #warning change mxn [-Wcpp]
7 | #warning change mxn
| ^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
460 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| 4 |
Correct |
1 ms |
468 KB |
Output is correct |
| 5 |
Correct |
1 ms |
468 KB |
Output is correct |
| 6 |
Correct |
1 ms |
468 KB |
Output is correct |
| 7 |
Correct |
1 ms |
468 KB |
Output is correct |
| 8 |
Correct |
1 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
460 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| 4 |
Correct |
1 ms |
468 KB |
Output is correct |
| 5 |
Correct |
1 ms |
468 KB |
Output is correct |
| 6 |
Correct |
1 ms |
468 KB |
Output is correct |
| 7 |
Correct |
1 ms |
468 KB |
Output is correct |
| 8 |
Correct |
1 ms |
468 KB |
Output is correct |
| 9 |
Correct |
4 ms |
732 KB |
Output is correct |
| 10 |
Correct |
3 ms |
716 KB |
Output is correct |
| 11 |
Correct |
4 ms |
724 KB |
Output is correct |
| 12 |
Correct |
4 ms |
724 KB |
Output is correct |
| 13 |
Correct |
4 ms |
724 KB |
Output is correct |
| 14 |
Correct |
3 ms |
724 KB |
Output is correct |
| 15 |
Correct |
2 ms |
724 KB |
Output is correct |
| 16 |
Correct |
4 ms |
724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
724 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
724 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
724 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
724 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
460 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| 4 |
Correct |
1 ms |
468 KB |
Output is correct |
| 5 |
Correct |
1 ms |
468 KB |
Output is correct |
| 6 |
Correct |
1 ms |
468 KB |
Output is correct |
| 7 |
Correct |
1 ms |
468 KB |
Output is correct |
| 8 |
Correct |
1 ms |
468 KB |
Output is correct |
| 9 |
Correct |
4 ms |
732 KB |
Output is correct |
| 10 |
Correct |
3 ms |
716 KB |
Output is correct |
| 11 |
Correct |
4 ms |
724 KB |
Output is correct |
| 12 |
Correct |
4 ms |
724 KB |
Output is correct |
| 13 |
Correct |
4 ms |
724 KB |
Output is correct |
| 14 |
Correct |
3 ms |
724 KB |
Output is correct |
| 15 |
Correct |
2 ms |
724 KB |
Output is correct |
| 16 |
Correct |
4 ms |
724 KB |
Output is correct |
| 17 |
Runtime error |
2 ms |
724 KB |
Execution killed with signal 11 |
| 18 |
Halted |
0 ms |
0 KB |
- |
