This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*input
6 5
1 2
3 6
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
*/
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
int main()
{
ios_base::sync_with_stdio(false);
ll n, m, s, t, u, v;
cin >> n >> m >> s >> t >> u >> v;
vector<pair<ll, ll>>adj[n + 1];
vector<ll>adj1[n + 1];
while (m--)
{
ll u, v, c;
cin >> u >> v >> c;
adj[u].push_back({v, c});
adj[v].push_back({u, c});
}
ll D[n + 1];
fill_n(D, n + 1, ll(1e18));
D[s] = 0;
priority_queue<pair<ll, ll>>Q;
Q.push({0, s});
vector<bool>jau(n + 1, false);
while (!Q.empty())
{
ll a = Q.top().second;
Q.pop();
if (jau[a])
continue;
jau[a] = true;
for (pair<ll, ll> b : adj[a])
{
if (D[b.first] > D[a] + b.second)
{
D[b.first] = D[a] + b.second;
Q.push({ -D[b.first], b.first});
}
}
}
vector<bool>buvau(n + 1, false);
queue<int>QQ;
QQ.push(t);
while (!QQ.empty())
{
ll a = QQ.front();
QQ.pop();
for (pair<ll, ll> b : adj[a])
{
if (D[b.first] == D[a] - b.second)
{
adj1[b.first].push_back(a);
adj1[a].push_back(b.first);
if (buvau[b.first] == false)
{
buvau[b.first] = true;
QQ.push(b.first);
}
}
}
}
fill_n(D, n + 1, ll(1e18));
D[u] = 0;
vector<bool>jau1(n + 1, false);
Q.push({ -1, u});
while (!Q.empty())
{
ll a = Q.top().second;
Q.pop();
if (jau1[a])
continue;
jau1[a] = true;
for (ll b : adj1[a])
{
if (D[b] > D[a])
{
D[b] = D[a];
Q.push({ -D[b], b});
}
}
for (pair<ll, ll> b : adj[a])
{
if (D[b.first] > D[a] + b.second)
{
D[b.first] = D[a] + b.second;
Q.push({ -D[b.first], b.first});
}
}
}
cout << D[v] << "\n";
}
# | 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... |