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;
};
void solve()
{
ll n, m;
cin >> n >> m;
ll s, t;
cin >> s >> t;
ll u, v;
cin >> u >> v;
vector<edge> adj[n + 1];
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);
}
pi from[n + 1] = {};
vi dist(n + 1, 1e15);
bool vis[n + 1] = {};
priority_queue<pi> pq;
pq.push({0, s});
dist[s] = 0;
from[s] = {0, -1};
while(!pq.empty()) {
ll x = pq.top().sc;
pq.pop();
if(vis[x]) continue;
vis[x] = true;
for(auto [y, w, id] : adj[x]) {
if(dist[y] > dist[x] + w) {
dist[y] = dist[x] + w;
pq.push({-dist[y], y});
from[y] = {x, id};
}
}
}
ll curr = t;
set<int> path;
while(curr != s) {
path.insert(from[curr].sc);
curr = from[curr].fr;
}
memset(vis, 0, sizeof(vis));
dist = vi(n + 1, 1e15);
dist[u] = 0;
pq.push({0, u});
while(!pq.empty()) {
int x = pq.top().sc;
pq.pop();
if(vis[x]) continue;
vis[x] = true;
for(auto [y, w, id] : adj[x]) {
if(path.count(id))
w = 0;
if(dist[y] > dist[x] + w) {
dist[y] = dist[x] + w;
pq.emplace(-dist[y], y);
}
}
}
cout << dist[v] << 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... |