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 ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 3e5 + 2;
const ll linf = 1e18;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
vector<int> u(m), v(m), w(m), suff(m);
vector<vector<pair<int, int>>> g(n);
for (int i = 0; i < m; i++) {
cin >> u[i] >> v[i] >> w[i];
u[i] -= 1; v[i] -= 1;
g[u[i]].push_back({v[i], i});
g[v[i]].push_back({u[i], i});
}
for (int i = m - 2; i >= 0; i--) suff[i] = min(suff[i + 1], w[i + 1]);
function<vector<ll>(int)> Dijk = [&] (int s) {
vector<ll> dist(n, linf);
priority_queue<pair<ll, int>> q;
q.push({0, s});
while (!q.empty()) {
auto s = q.top(); q.pop();
s.first *= -1;
if (dist[s.second] <= s.first) continue;
dist[s.second] = s.first;
for (auto u : g[s.second]) {
if (dist[u.first] == linf) q.push({-s.first - w[u.second], u.first});
}
}
return dist;
};
vector<ll> a = Dijk(0);
vector<ll> b = Dijk(n - 1);
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... |