이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#ifndef LOCAL
#define NDEBUG 1
#endif // LOCAL
#include<bits/stdc++.h>
#define i64 int64_t
const i64 inf=1e17;
const int max_n=100000;
std::vector< std::pair<int, int> > adjList[max_n];
i64 dist_u[max_n], dist_v[max_n], dist_s[max_n];
bool visited[max_n];
i64 dp[2][max_n];
i64 result;
void dijkstra(int start, i64 dist[]) {
std::priority_queue< std::pair<i64, int> > pq;
memset(visited, false, sizeof(visited));
pq.push({0, start});
while (!pq.empty()) {
i64 cdist=pq.top().first;
int cvertex=pq.top().second;
pq.pop();
if (!visited[cvertex]) {
visited[cvertex]=true;
dist[cvertex]=-cdist;
for (auto& to: adjList[cvertex]) {
pq.push({cdist-to.second, to.first});
}
}
}
}
void dijkstra2(int start, int finish) {
std::fill(dp[0], dp[0]+max_n, inf);
std::fill(dp[1], dp[1]+max_n, inf);
memset(visited, false, sizeof(visited));
std::priority_queue< std::pair< i64, std::pair<int, int> > > pq;
pq.push({0, {start, 0}});
while (!pq.empty()) {
i64 cdist=pq.top().first;
int cvertex=pq.top().second.first;
int cpar=pq.top().second.second;
pq.pop();
if (!visited[cvertex]) {
visited[cvertex]=true;
dist_s[cvertex]=-cdist;
dp[0][cvertex]=std::min(dist_u[cvertex], dp[0][cpar]);
dp[1][cvertex]=std::min(dist_v[cvertex], dp[1][cpar]);
for (auto& to: adjList[cvertex]) {
pq.push({cdist-to.second, {to.first, cvertex}});
}
}
else {
if (std::min(dist_u[cvertex], dp[0][cpar])+std::min(dist_v[cvertex], dp[1][cpar])<=dp[0][cvertex]+dp[1][cvertex]) {
dp[0][cvertex]=std::min(dist_u[cvertex], dp[0][cpar]);
dp[1][cvertex]=std::min(dist_v[cvertex], dp[1][cpar]);
}
}
}
/*while (!pq.empty()) {
int cdist=-pq.top().first;
int cvertex=pq.top().second.first;;
int cpar=pq.top().second.second;
pq.pop();
if (dist_s[cvertex]<cdist) continue;
for (auto& to: adjList[cvertex]) {
i64 new_dist=cdist+to.second;
if (dist_s[to.first]>new_dist) {
pq.push({-(dist_s[to.first]=new_dist), {to.first, cvertex}});
dp[0][cvertex]=std::min(dist_u[cvertex], dp[0][cpar]);
dp[1][cvertex]=std::min(dist_v[cvertex], dp[1][cpar]);
}
else {
if (dist_s[to.first]==new_dist and
std::min(dist_u[cvertex], dp[0][cpar])+std::min(dist_v[cvertex], dp[1][cpar])<=dp[0][cvertex]+dp[1][cvertex]) {
dp[0][cvertex]=std::min(dist_u[cvertex], dp[0][cpar]);
dp[1][cvertex]=std::min(dist_v[cvertex], dp[1][cpar]);
}
}
}
}*/
result=std::min(result, dp[0][finish]+dp[1][finish]);
}
int main() {
std::ios_base::sync_with_stdio(0); std::cin.tie(0);
int n, m, s, t, u, v;
std::cin>>n>>m>>s>>t>>u>>v;
--s, --t, --u, --v;
for (int i=0; i<m; ++i) {
int a, b, c; std::cin>>a>>b>>c;
--a, --b;
adjList[a].push_back({b, c});
adjList[b].push_back({a, c});
}
dijkstra(u, dist_u);
dijkstra(v, dist_v);
result=dist_u[v];
dijkstra2(s, t);
dijkstra2(t, s);
std::cout<<result;
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... |