이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
#include <climits>
#include <cmath>
#include <set>
#include <algorithm>
#include <stack>
using namespace std;
#define speedup ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define ll long long
vector<ll> distU, distV;
vector<vector<pair<ll, ll>>> graph;
ll n, m;
ll s, t;
ll u, v;
vector<ll> dijstra(ll st){
vector<ll> dist(n, LLONG_MAX/2);
dist[st] = 0;
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
pq.push({0, st});
vector<bool> vis(n, false);
while (!pq.empty()){
ll c = pq.top().second; pq.pop();
vis[c] = true;
for (pair<ll, ll> p: graph[c]){
if (!vis[p.first] && dist[p.first] > dist[c]+p.second){
dist[p.first] = dist[c]+p.second;
pq.push({dist[p.first], p.first});
}
}
}
return dist;
}
ll dijstra2(ll start, ll end){
vector<ll> dU(n, LLONG_MAX/2), dV(n, LLONG_MAX/2);
vector<ll> dist(n, LLONG_MAX/2);
priority_queue<pair<ll, pair<ll, ll>>, vector<pair<ll, pair<ll, ll>>>, greater<pair<ll, pair<ll, ll>>>> pq;
pq.push({0, {start, 0}});
dist[start] = 0;
vector<bool> vis(n, false);
while (!pq.empty()){
ll cdist = pq.top().first; ll cur = pq.top().second.first, par = pq.top().second.second; pq.pop();
if (!vis[cur]){
vis[cur] = true;
dist[cur] = cdist;
dU[cur] = min(distU[cur], dU[par]);
dV[cur] = min(distV[cur], dV[par]);
for (pair<ll, ll> p: graph[cur]){
pq.push({cdist+p.second, {p.first, cur}});
}
}else if (cdist == dist[cur] && min(dU[par], distU[cur])+min(dV[par], distV[cur]) <= dU[cur]+dV[cur]){
dU[cur] = min(distU[cur], dU[par]);
dV[cur] = min(distV[cur], dV[par]);
}
}
return dU[end]+dV[end];
}
int main(){
speedup
cin >> n >> m;
cin >> s >> t;
cin >> u >> v;
graph.resize(n);
s--, t--, u--, v--;
for (ll i = 0; i < m; i++){
ll a, b, w; cin >> a >> b >> w;
a--, b--;
graph[a].push_back({b, w});
graph[b].push_back({a, w});
}
distU = dijstra(u);
distV = dijstra(v);
ll a1 = dijstra2(s, t);
ll a2 = dijstra2(t, s);
cout << min(distU[v], min(a1, a2)) << 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... |