이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// subtask 2
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
#define endl '\n'
#define pl(var) " [" << #var << ": " << (var) << "] "
#define ll long long
ll int inf = 1e16;
void solve() {
int n, m; cin >> n >> m;
int s, t; cin >> s >> t;
int U, V; cin >> U >> V;
s--; t--; U--; V--;
vector<vector<pair<int, ll int>>> adj(n);
vector<vector<ll int>> wt(n, vector<ll int>(n, inf));
for (int i = 0; i < m; i++) {
int a, b; ll int c; cin >> a >> b >> c;
a--; b--;
wt[a][b] = c;
wt[b][a] = c;
adj[a].emplace_back(b, c);
adj[b].emplace_back(a, c);
}
{
vector<int> came_from(n, -1);
vector<ll int> dist(n, inf);
dist[s] = 0;
priority_queue<pair<ll int, int>> pq;
pq.emplace(0, s);
while (pq.size() != 0) {
int u = pq.top().second;
ll int cur_dist = pq.top().first * -1;
pq.pop();
if (dist[u] != cur_dist) continue;
for (auto [v, cost] : adj[u]) {
ll int new_dist = cur_dist + cost;
if (new_dist < dist[v]) {
dist[v] = new_dist;
came_from[v] = u;
pq.emplace(-new_dist, v);
}
}
}
// assert(came_from[t] != -1);
int node = t;
while (node != -1) {
int prev = came_from[node];
if (prev == -1) break;
wt[prev][node] = 0;
wt[node][prev] = 0;
node = prev;
}
vector<vector<pair<int, ll int>>> new_adj(n);
for (int i = 0; i < n; i++) {
// new_adj[i].emplace_back(a)
for (auto [v, _] : adj[i]) {
new_adj[i].emplace_back(v, wt[i][v]);
}
}
adj = new_adj;
}
// now run a djkstra from U to V
vector<ll int> dist(n, inf);
dist[U] = 0;
priority_queue<pair<ll int, int>> pq;
pq.emplace(0, U);
while (pq.size() != 0) {
int u = pq.top().second;
ll int cur_dist = pq.top().first * -1;
pq.pop();
for (auto [v, cost] : adj[u]) {
ll int new_dist = cur_dist + cost;
if (new_dist < dist[v]) {
dist[v] = new_dist;
pq.emplace(-new_dist, v);
}
}
}
// assert(dist[V] < inf);
cout << dist[V] << endl;
}
int main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
// cin >> T;
while (T--)
solve();
}
# | 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... |