This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// author: gary
// created: 2018/09/03 13:29:03
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <limits>
#include <utility>
#include <functional>
#include <string>
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
using namespace std;
#define SZ(x) ( (int) (x).size() )
#define ALL(c) (c).begin(), (c).end()
#define CNT(c, x) ((c).find(x) != (c).end())
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
template<class T> bool cmax(T& a, T b) { if(a < b) { a = b; return true; } return false; }
template<class T> bool cmin(T& a, T b) { if(a > b) { a = b; return true; } return false; }
const int INF = 1e9;
const int N = 200005;
int n, m, S, T, U, V;
vector<pii> E[N];
ll d[2][N]; // d[U][.] and d[V][.]
void dijkstra(ll* dist, int u) {
priority_queue<pli, vector<pli>, greater<pli>> pq;
fill(dist, dist + N, 1LL<<62);
dist[u] = 0;
pq.push(mp(0, u));
while(!pq.empty()) {
pli t = pq.top();
pq.pop();
if(dist[t.second] < t.first) {
continue;
}
for(auto& e: E[t.second]) {
if(cmin(dist[e.first], t.first + e.second)) {
pq.push(mp(dist[e.first], e.first));
}
}
}
}
ll dist[N];
ll min_d[2][N];
ll min_sum[N];
ll calc(int U, int V) {
priority_queue<pli, vector<pli>, greater<pli>> pq;
fill(dist, dist + N, 1LL<<62);
fill(min_sum, min_sum + N, 1LL<<62);
for(int i = 1; i <= n; i++) {
min_sum[i] = 1LL<<62;
min_d[0][i] = min_d[1][i] = 1LL<<62;
}
dist[U] = 0;
min_sum[U] = d[0][U] + d[1][U];
min_d[0][U] = d[0][U];
min_d[1][U] = d[1][U];
pq.push(mp(0LL, U));
while(!pq.empty()) {
pli t = pq.top();
pq.pop();
int u = t.second;
ll cost = t.first;
if(dist[u] < cost) {
continue;
}
for(auto& e: E[u]) {
int v = e.first;
ll ndist = cost + e.second;
if(dist[v] < ndist) {
continue;
}
if(dist[v] > ndist) {
for(int i = 0; i < 2; i++) {
min_d[i][v] = d[i][v];
}
min_sum[v] = 1LL << 62;
dist[v] = ndist;
pq.push(mp(dist[v], v));
}
cmin(min_d[0][v], min_d[0][u]);
cmin(min_d[1][v], min_d[1][u]);
cmin(min_sum[v], min_d[0][v] + d[1][v]);
cmin(min_sum[v], min_d[1][v] + d[0][v]);
cmin(min_sum[v], min_sum[u]);
}
}
/*
for(int i = 1; i <= n; i++) {
printf("min_sum: %d %lld\n", i, min_sum[i]);
}
*/
return min(d[0][V], min_sum[V]);
}
int main() {
cin >> n >> m >> S >> T >> U >> V;
for(int i = 0; i < m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
E[u].emplace_back(v, w);
E[v].emplace_back(u, w);
}
dijkstra(d[0], U);
dijkstra(d[1], V);
// for(int i = 1; i <= n; i++) { printf("%lld %lld\n", d[0][i], d[1][i]); }
printf("%lld\n", calc(S, T));
return 0;
}
Compilation message (stderr)
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:128:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &u, &v, &w);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
# | 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... |