#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <algorithm>
#include <bitset>
#define ll long long
#define vi vector<int>
#define pii pair<ll, int>
#define ppi pair<ll, pii>
#define fst first
#define snd second
#define pub push_back
#define vpi vector<pii>
using namespace std;
namespace fastIO
{
char outString[64];
inline int getchar_unlocked() {return getchar();}
inline void putchar_unlocked(int x) {putchar(x);}
inline int charInput() {return getchar_unlocked();}
inline void charOutput(int x) {putchar_unlocked(x);}
inline bool isNum(int c) {return '0' <= c && c <= '9';}
inline int intInput()
{
int c = 0, ret = 0; bool neg = 0;
while (!isNum(c))
{
c = getchar_unlocked();
if (c == '-') {neg = 1;}
}
while (isNum(c)) {ret = ret * 10 + c - '0'; c = getchar_unlocked();}
return (neg) ? -ret : ret;
}
inline void intOutput(ll x)
{
int ss = 0;
while (x) {outString[ss++] = x % 10 + '0'; x /= 10;}
if (!ss) outString[ss++] = '0';
for (int i = ss - 1; i >= 0; i--) putchar_unlocked(outString[i]);
}
inline void strOutput(string s)
{
for (auto &c : s) putchar_unlocked(c);
}
}
const ll INF = 1e17;
int n, m, pref[300069], cst[300069], idx = 0, vis[300069], low[300069], clr[300069];
vpi adj[300069];
pii edge[300069];
ppi sedg[300069];
ll dst[2][300069], de[2][300069], lim;
priority_queue<pii, vector<pii>, greater<pii>> pq;
bool ans = 0;
inline void runDijkstra(int s, int id)
{
for (int i = 0; i < n; i++) dst[id][i] = INF;
dst[id][s] = 0;
pq.push({0, s});
while (pq.size())
{
ll d = pq.top().fst; int u = pq.top().snd; pq.pop();
if (d == dst[id][u])
{
for (auto v : adj[u])
{
if (dst[id][u] + cst[v.fst] < dst[id][v.snd])
{
dst[id][v.snd] = dst[id][u] + cst[v.fst];
pq.push({dst[id][v.snd], v.snd});
}
}
}
}
}
void bCheck(int u, int p)
{
clr[idx] = u;
vis[u] = low[u] = idx++;
for (auto v : adj[u])
{
if (de[0][v.fst] > lim) break;
if (v.snd != p)
{
if (vis[v.snd] == -1)
{
bCheck(v.snd, u);
if (ans) return;
low[u] = min(low[v.snd], low[u]);
}
else low[u] = min(vis[v.snd], low[u]);
if (low[v.snd] > vis[u] && (vis[n - 1] != -1 && low[v.snd] <= vis[n - 1]) && de[1][v.fst] > lim) {ans = 1; return;}
}
}
}
inline bool comp(const pii &l, const pii &r)
{
return make_pair(de[0][l.fst], l) < make_pair(de[0][r.fst], r);
}
int32_t main()
{
// ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen("5-1.in", "r", stdin);
n = fastIO :: intInput();
m = fastIO :: intInput();
for (int i = 0; i < n; i++) vis[i] = -1;
for (int i = 0; i < m; i++)
{
int u, v, w;
u = fastIO :: intInput();
v = fastIO :: intInput();
w = fastIO :: intInput();
u--; v--;
adj[u].push_back({i, v});
adj[v].push_back({i, u});
cst[i] = pref[i] = w;
edge[i] = {u, v};
}
for (int i = m - 2; i >= 0; i--) {pref[i] = max(pref[i], pref[i + 1]);}
runDijkstra(0, 0);
runDijkstra(n - 1, 1);
for (int i = 0; i < m; i++)
{
de[0][i] = min(dst[0][edge[i].fst] + dst[1][edge[i].snd], dst[1][edge[i].fst] + dst[0][edge[i].snd]) + cst[i];
de[1][i] = de[0][i] + pref[i + 1];
}
for (int i = 0; i < n; i++) {sort(adj[i].begin(), adj[i].end(), comp);}
ll L = dst[0][n - 1], R = dst[0][n - 1] + 1000000000;
while (L < R)
{
int M = L + R >> 1; idx = 0; lim = M; ans = 0;
bCheck(0, -1);
if (ans) L = M + 1;
else R = M;
for (int i = 0; i < idx; i++) {vis[clr[i]] = -1;}
}
fastIO :: intOutput(L);
fastIO :: charOutput('\n');
return 0;
}
Compilation message
Aesthetic.cpp: In function 'int32_t main()':
Aesthetic.cpp:141:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int M = L + R >> 1; idx = 0; lim = M; ans = 0;
~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
7424 KB |
Output is correct |
| 2 |
Correct |
6 ms |
7424 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
7424 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
7424 KB |
Output is correct |
| 2 |
Correct |
6 ms |
7424 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
7424 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
708 ms |
42832 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
688 ms |
43308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2077 ms |
51028 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2077 ms |
51028 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
7424 KB |
Output is correct |
| 2 |
Correct |
6 ms |
7424 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
7424 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
