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>
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define MAX_N 100000
#define xx first
#define yy second
using namespace std;
typedef long long lint;
//ifstream cin("04-08.txt");
//ofstream cout("out.txt");
const lint sqrInf = (1e18) - 1;
lint rez;
int n, m;
int s, t;
int u, v;
vector <pair<int, int>> g[MAX_N + 1];
void add(int a, int b, int c)
{
g[a].push_back({b, c});
}
int viz[MAX_N + 1][4];
lint dist[MAX_N + 1][4];
lint dp[MAX_N + 1][4];
int vi[MAX_N + 1][4];
priority_queue <pair<lint, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
struct elem
{
lint d;
int nod, x;
};
void readFile()
{
cin >> n >> m;
cin >> s >> t;
cin >> u >> v;
for(int i = 1; i <= m; i ++)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
add(b, a, c);
}
}
void distra(int x, int cr)
{
while(q.size() > 0)
q.pop();
for(int i = 1; i <= n; i ++)
dist[i][cr] = sqrInf;
dist[x][cr] = 0;
q.push({0, x});
while(q.size() > 0)
{
int a = q.top().yy;
q.pop();
if(viz[a][cr] == 0)
{
viz[a][cr] = 1;
for(auto u : g[a])
{
if(dist[a][cr] + u.yy < dist[u.xx][cr])
{
dist[u.xx][cr] = dist[a][cr] + u.yy;
q.push({dist[u.xx][cr], u.xx});
}
}
}
}
}
int okEdge(int a, int b, int c)
{
if(dist[a][0] + dist[b][1] + c == dist[t][0])
return 1;
if(dist[a][1] + dist[b][0] + c == dist[t][0])
return 1;
return 0;
}
bool verif(int a, int b, int cr)
{
return (dist[a][cr - 1] > dist[b][cr - 1]);
}
void getDp()
{
auto cmp = [](elem x, elem y) {return (x.d > y.d); };
std::priority_queue<elem, std::vector<elem>, decltype(cmp)> q(cmp);
while(q.size() > 0)
q.pop();
for(int i = 1; i <= n; i ++)
{
for(int j = 0; j <= 3; j ++)
dp[i][j] = sqrInf;
}
dp[u][0] = 0;
q.push({0, u, 0});
while(q.size() > 0)
{
int a = q.top().nod;
int cr = q.top().x;
q.pop();
if(vi[a][cr] == 0)
{
vi[a][cr] = 1;
if(cr == 0 || cr == 1 || cr == 2 || cr == 3)
{
///0-0 and 3-3 and 1-3 and 2-3
int w = ((cr == 1 || cr == 2) ? 3 : cr);
for(auto u : g[a])
{
if(dp[a][cr] + u.yy < dp[u.xx][w])
{
dp[u.xx][w] = dp[a][cr] + u.yy;
q.push({dp[u.xx][w], u.xx, w});
}
}
}
if(cr == 0)
{
for(auto u : g[a])
{
if(okEdge(a, u.xx, u.yy))
{
for(int h = 1; h <= 2; h ++)
{
if(verif(a, u.xx, h))
if(dp[a][cr] < dp[u.xx][h])
{
dp[u.xx][h] = dp[a][cr];
q.push({dp[u.xx][h], u.xx, h});
}
}
}
}
}
if(cr == 1 || cr == 2)
{
///1-1 and 2-2
for(auto u : g[a])
{
if(okEdge(a, u.xx, u.yy) && verif(a, u.xx, cr))
{
if(dp[a][cr] < dp[u.xx][cr])
{
dp[u.xx][cr] = dp[a][cr];
q.push({dp[u.xx][cr], u.xx, cr});
}
}
}
}
}
}
rez = min({dp[v][0], dp[v][1], dp[v][2], dp[v][3]});
}
void solve()
{
distra(s, 0);
distra(t, 1);
/* distra(v, 2);
lint mn = sqrInf;
for(int i = 1; i <= n; i ++)
{
if(dist[i][0] + dist[i][1] == dist[t][0])
mn = min(mn, dist[i][2]);
}
cout << mn << "\n";*/
getDp();
}
void printFile()
{
cout << rez << "\n";
}
int main()
{
readFile();
solve();
printFile();
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... |