This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#define MAXN 100005
#define LL long long
using namespace std;
int N, M, A, B, U, V;
LL db[MAXN], du[MAXN], dv[MAXN];
LL da[MAXN], umin[MAXN], best = 1LL<<60;
vector <pair<int,LL> > adj[MAXN];
priority_queue <pair<LL,int> > PQ;
void dijkstra(int src, LL* d) {
for (int i=1; i<=N; i++) {
d[i] = 1LL<<60;
}
d[src] = 0;
PQ.push({0, src});
while (PQ.size()) {
LL w = -PQ.top().first, v = PQ.top().second;
PQ.pop();
if (w != d[v]) {continue;}
for (auto e: adj[v]) {
if (e.second + d[v] < d[e.first]) {
d[e.first] = e.second + d[v];
PQ.push({-d[e.first], e.first});
}
}
}
}
void slv() {
for (int i=1; i<=N; i++) {
da[i] = 1LL<<60;
umin[i] = du[i];
}
da[A] = 0, umin[A] = du[A]; //need relax d(u,v)?
PQ.push({0, A});
while (PQ.size()) {
LL w = -PQ.top().first, v = PQ.top().second;
PQ.pop();
if (w != da[v]) {continue;}
for (auto e: adj[v]) {
if (e.second + da[v] < da[e.first]) {
da[e.first] = e.second + da[v];
umin[e.first] = min(du[e.first], umin[v]);
PQ.push({-da[e.first], e.first});
} else if (e.second + da[v] == da[e.first]) {
umin[e.first] = min(du[e.first], min(umin[e.first],umin[v]));
}
}
if (da[v] + db[v] == db[A]) {
best = min(best, umin[v] + dv[v]);
}
}
}
int main() {
//freopen("passin.txt","r",stdin);
scanf("%d %d\n%d %d\n%d %d",&N,&M,&A,&B,&U,&V);
for (int i=0; i<M; i++) {
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
adj[a].push_back({b,c});
adj[b].push_back({a,c});
}
dijkstra(B, db);
dijkstra(U, du);
dijkstra(V, dv);
best = du[V];
slv();
swap(A,B);
for (int i=1; i<=N; i++) {
db[i] = da[i];
}
slv();
printf("%lld",best);
}
Compilation message (stderr)
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
61 | scanf("%d %d\n%d %d\n%d %d",&N,&M,&A,&B,&U,&V);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
64 | scanf("%d %d %d",&a,&b,&c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
# | 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... |