#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<vector<pair<long long,pair<int,int>>>>g(3e5+5);
vector<long long>dp2(3e5+5,1e9+5);
vector<long long>dp(3e5+5,0);
void dfs(int v=1,int p=-1,int w=0)
{
if(p==-1)dp[v] = 0;
else dp[v] = dp[p] + w;
for(auto u : g[v])
{
if(p != u.second.first)
{
dp2[u.second.first]= min(dp2[v],u.second.second);
dfs(u.second.first,v,u.first);
}
}
}
signed main()
{
int n,m;
cin >> n>>m;
// cin >> n >> m;
vector<long long>mx(m+2);
for(int i = 1;i<=m;i++)
{
int a,b,w;
cin >> a >> b >> w;
//cout << 'o';
g[a].push_back({w,{b,i}});
g[b].push_back({w,{a,i}});
mx[i] = w;
//cout << 'o';
}
for(int i = n-1;i> 0;i--)
{
mx[i] = max(mx[i+1],mx[i]);
}
dfs();
long long ans = dp[n] + mx[dp2[n]+1];
cout << ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
582 ms |
1048576 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
582 ms |
1048576 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
285 ms |
41552 KB |
Output is correct |
2 |
Correct |
297 ms |
41812 KB |
Output is correct |
3 |
Correct |
298 ms |
41288 KB |
Output is correct |
4 |
Correct |
296 ms |
41300 KB |
Output is correct |
5 |
Correct |
289 ms |
41548 KB |
Output is correct |
6 |
Correct |
301 ms |
42292 KB |
Output is correct |
7 |
Correct |
297 ms |
42068 KB |
Output is correct |
8 |
Correct |
307 ms |
42308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2041 ms |
43640 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
897 ms |
1048576 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
897 ms |
1048576 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
582 ms |
1048576 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |