#include <bits/stdc++.h>
using namespace std;
vector<pair<long long, long long>> graph[100007];
vector<pair<long long, long long>> graph2[200007];
long long odl[100007][2];// s t u v
long long odl2[100007][2];// s t u v
long long n;
void djikstra(long long s, long long kt)
{
for(long long i = 1; i <= n; i++)
{
odl[i][kt] = LLONG_MAX;
}
odl[s][kt] = 0;
priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>> pq;
pq.push({0, s});
while(!pq.empty())
{
auto cur = pq.top();
pq.pop();
for(auto x : graph[cur.second])
{
if(odl[x.first][kt] > odl[cur.second][kt] + x.second)
{
odl[x.first][kt] = odl[cur.second][kt] + x.second;
pq.push({odl[x.first][kt], x.first});
}
}
}
}
void djikstra2(long long s, long long kt)
{
for(long long i = 1; i <= n; i++)
{
odl[i][kt] = LLONG_MAX;
}
odl2[s][kt] = 0;
priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>> pq;
pq.push({0, s});
while(!pq.empty())
{
auto cur = pq.top();
pq.pop();
for(auto x : graph2[cur.second])
{
if(odl2[x.first][kt] > odl2[cur.second][kt] + x.second)
{
odl2[x.first][kt] = odl2[cur.second][kt] + x.second;
pq.push({odl2[x.first][kt], x.first});
}
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
long long m, s, t, u, v;
cin >> n >> m >> s >> t >> u >> v;
for(long long i = 0; i < m; i++)
{
long long a, b, c;
cin >> a >> b >> c;
graph[a].push_back({b, c});
graph[b].push_back({a, c});
graph2[a].push_back({b, c});
graph2[b].push_back({a, c});
graph2[a + 100000].push_back({b + 100000, c});
graph2[b + 100000].push_back({a + 100000, c});
}
djikstra(s, 0);
djikstra(t, 1);
for(long long i = 1; i <= n; i++)
{
for(auto x : graph[i])
{
if(odl[i][0] + odl[x.first][1] + x.second == odl[t][0] && odl[i][0] < odl[x.first][0])
{
graph2[i].push_back({x.first + 100000, 0});
}
}
}
djikstra2(u, 0);
djikstra2(v, 1);
cout << min(min(odl[v][0], odl[u][1]), min(odl[v + 100000][0], odl[u + 100000][1])) << endl;
return 0;
}
# | 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... |