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 "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll, ll> pi;
#define FOR(i, j, k) for (ll i = j; i < (ll) k; ++i)
#define FORD(i, j, k) for (ll i = j; i >= (ll) k; --i)
#define nl "\n"
#define sp " "
#define all(x) (x).begin(), (x).end()
#define sc second
#define fr first
#define pb emplace_back
struct edge {
ll b, w;
ll id;
};
const int mxN = 1e5 + 5;
ll n, m;
vector<edge> adj[mxN];
vi djik(int x) {
vi dist(n + 1, 1e15);
bool vis[n + 1] = {};
priority_queue<pi> pq;
dist[x] = 0;
pq.emplace(0, x);
while(!pq.empty()) {
int u = pq.top().sc;
pq.pop();
if(vis[u]) continue;
vis[u] = true;
for(auto [v, w, id] : adj[u]) {
if(dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.emplace(-dist[v], v);
}
}
}
return dist;
}
void solve()
{
cin >> n >> m;
ll s, t;
cin >> s >> t;
ll u, v;
cin >> u >> v;
FOR(i, 0, m) {
ll a, b, c;
cin >> a >> b >> c;
edge curr;
curr.b = b;
curr.w = c;
curr.id = i;
adj[a].pb(curr);
curr.b = a;
adj[b].pb(curr);
}
vi distS = djik(s);
vi distT = djik(t);
vi distV = djik(v);
ll mn = distS[t];
ll ans = 1e15;
FOR(i, 1, n + 1) {
if(distS[i] + distT[i] == mn) {
ans = min(ans, distV[i]);
}
}
cout << ans << nl;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t = 1;
// cin >> t;
while (t--)
{
solve();
}
}
# | 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... |