| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1042310 | DeathIsAwe | Commuter Pass (JOI18_commuter_pass) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
void dijkstra(ll n, ll a, vector<vector<pair<ll,ll>>> &graph, vector<ll> &from) {
priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
vector<bool> solved(n);
for (int i=0;i<n;i++) {
if (i == a) {
pq.push(make_pair(0, i));
} else {
pq.push(make_pair(INT64_MAX, i));
}
solved[i] = false;
from[i] = INT64_MAX;
}
from[a] = 0;
pair<ll,ll> node;
while (pq.size() > 0) {
node = pq.top(); pq.pop();
if (solved[node.second]) {
continue;
}
solved[node.second] = true;
for (pair<ll,ll> i: graph[node.second]) {
if (!solved[i.first]) {
if (from[i.first] > from[node.second] + i.second) {
from[i.first] = from[node.second] + i.second;
pq.push(make_pair(from[i.first], i.first));
}
}
}
}
}
int main() {
ll n, m, s, t, u, v; cin >> n >> m >> s >> t >> u >> v;
ll a, b, c;
s--; t-- ; u--; v--;
vector<ll> froms(n), fromt(n), fromu(n), fromv(n);
priority_queue<pair<ll,ll>> pq;
vector<vector<pair<ll,ll>>> graph(n);
for (int i=0;i<m;i++) {
cin >> a >> b >> c;
graph[a-1].push_back(make_pair(b-1, c));
graph[b-1].push_back(make_pair(a-1, c));
}
dijkstra(n, s, graph, froms);
dijkstra(n, t, graph, fromt);
dijkstra(n, u, graph, fromu);
dijkstra(n, v, graph, fromv);
ll mindis = froms[t];
vector<pair<ll,ll>> goodnodes;
vector<bool> visited(n);
for (int i=0;i<n;i++) {
if (froms[i] + fromt[i] == mindis) {
goodnodes.push_back(make_pair(fromu[i], i));
}
visited[i] = false;
}
sort(goodnodes.begin(),goodnodes.end());
vector<pair<ll,ll>> stac;
vector<ll> dpuforward(n, INT64_MAX), dpureturn(n, INT64_MAX);
pair<ll,ll> node;
for (pair<ll,ll> i: goodnodes) {
if (visited[i.second]) {
continue;
}
dpuforward[i.second] = i.first; dpureturn[i.second] = i.first;
visited[i.second] = true;
stac.clear(); stac.push_back(make_pair(i.second, 0));
while (stac.size() > 0) {
node = stac.back(); stac.pop_back();
for (pair<ll,ll> j: graph[node.first]) {
if (visited[j.first]) {
continue;
}
if (froms[j.first] + j.second + fromt[node.first] == mindis) {
if (node.second < 1) {
stac.push_back(make_pair(j.first, -1));
dpureturn[j.first] = i.first;
visited[j.first] = true;
}
} else if (fromt[j.first] + j.second + froms[node.first] == mindis) {
if (node.second > -1) {
stac.push_back(make_pair(j.first, 1));
dpuforward[j.first] = i.first;
visited[j.first] = true;
}
}
}
}
}
ll ans = fromv[u];
for (pair<ll,ll> i: goodnodes) {
ans = min(ans, fromv[i.second] + min(dpuforward[i.second], dpureturn[i.second]));
}
cout << ans;
}