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 <iostream>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
#define int long long
using namespace std;
signed main(){
int N, M;
cin >> N >> M;
vector<vector<pair<int, int>>> tree(N);
vector<int> vals(M);
for(int i = 0; i < M; i ++){
int a, b, c;
cin >> a >> b >> c;
a--;
b--;
tree[a].push_back({b,i});
tree[b].push_back({a,i});
vals[i] = c;
}
int an = 0;
for(int i = 0; i < M-1; i ++){
int tval = *max_element(vals.begin()+i+1, vals.end());
vals[i] += tval;
priority_queue<vector<int>> que;
que.push({0,0});
int ans = 0;
vector<bool> vis(N);
while(!que.empty()){
int a = -que.top()[0], b = que.top()[1];
que.pop();
if(b == N-1){ans = a; break;}
if(vis[b])continue;
vis[b] = true;
for(auto [l, r] : tree[b]){
que.push({-a-vals[r], l});
}
}
an = max(an, ans);
vals[i] -= tval;
}
cout << an << endl;
return 0;
}
# | 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... |