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 <bits/stdc++.h>
#define F first
#define S second
#define mp make_pair
#define pb push_back
//#define ll __int128
#define ll long long
#define int long long
#define LEFT(a) ((a)<<1)
#define RIGHT(a) (LEFT(a) + 1)
#define MID(a,b) ((a+b)>>1)
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define y1 y122
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
/*
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target ("avx2")
#pragma GCC optimization ("unroll-loops")
#pragma comment(linker, "/STACK: 20000000005")
*/
using namespace std;
const int N = 300005, INF = 5e14;
int n, m;
int u[N], v[N], x[N], y[N];
int dp[N][2];
bool F[N][2];
vector < pair < int, pair < int, int > > > G[N];
priority_queue < pair < int, pair < int, int > > > Q;
main()
{
//freopen ("in.in", "r", stdin);freopen ("out.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin >> n >> m;
for (int i = 1; i <= m; i++){
cin >> u[i] >> v[i] >> x[i];
}
for (int i = m; i >= 1; i--){
y[i] = max (x[i+1], y[i+1]);
G[u[i]].pb ({v[i], {x[i], y[i]}});
G[v[i]].pb ({u[i], {x[i], y[i]}});
}
for (int i = 2; i <= n; i++)
dp[i][0] = dp[i][1] = INF;
dp[1][0] = 0;
dp[1][1] = 0;
Q.push ({0, {1, 0}});
Q.push ({0, {1, 1}});
while (Q.size() > 0){
int k = Q.top().S.F, ch = Q.top().S.S, D;
Q.pop();
if (F[k][ch])
continue;
F[k][ch] = 1;
for (auto it : G[k]){
int to = it.F;
if (ch == 0){
D = dp[k][0] + it.S.F;
if (D < dp[to][0]){
dp[to][0] = D;
Q.push ({-D, {to, 0}});
}
}
else {
D = it.S.F + max (dp[k][0] + it.S.S, dp[k][1]);
if (D < dp[to][1]){
dp[to][1] = D;
Q.push ({-D, {to, 1}});
}
}
}
}
cout << dp[n][1] << endl;
}
Compilation message (stderr)
Aesthetic.cpp:18: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
18 | #pragma GCC optimization ("unroll-loops")
|
Aesthetic.cpp:44:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
44 | main()
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |