#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxn 100002
#define maxm 200002
int n, m, s, t, u, v;
vector<int> parents[maxn]; //the first one stores the parents using the dijkstras thing for source S, the second one stores with source T
vector<pair<int, ll> > adj[maxn]; //first one is the id, second one is the cost of the edge //max cost is one billion
ll dist[maxn][3]; //the first one stores the distances from source S, the second stores from Source U, the third one stores from Source V
vector<int> shortpathchildren[maxn];
vector<int> dagnodes;
bool vis[maxn];
ll dpU[maxn][2]; //dpU[i] gives the minimum distance from U to any vertex between i and S
ll dpV[maxn][2]; //dpV[i] gives the minimum distance from V to any vertex between i and T
ll dpUfuncone(int i)
{
if (dpU[i][0] != LLONG_MAX)
{
return dpU[i][0];
}
if (i == s)
{
return dist[s][1];
}
ll temp = dist[i][1];
for (auto j: parents[i])
{
temp = min(temp, dpUfuncone(j));
}
// if (temp < 0)
// {
// cerr << i << " " << temp << endl;
// }
return dpU[i][0] = temp;
}
ll dpVfuncone(int i)
{
if (dpV[i][0] != LLONG_MAX)
{
return dpV[i][0];
}
if (i == t)
{
//cerr << "YES: " << dist[t][2] << endl;
return dist[t][2];
}
ll temp = dist[i][2];
for (auto j: shortpathchildren[i])
{
temp = min(temp, dpVfuncone(j));
}
return dpV[i][0] = temp;
}
ll dpUfunctwo(int i)
{
if (dpU[i][1] != LLONG_MAX)
{
return dpU[i][1];
}
if (i == t)
{
return dist[t][1];
}
ll temp = dist[i][1];
for (auto j: shortpathchildren[i])
{
temp = min(temp, dpUfunctwo(j));
}
return dpV[i][1] = temp;
}
ll dpVfunctwo(int i)
{
if (dpU[i][1] != LLONG_MAX)
{
return dpU[i][0];
}
if (i == s)
{
return dist[s][2];
}
ll temp = dist[i][2];
for (auto j: parents[i])
{
temp = min(temp, dpVfunctwo(j));
}
return dpV[i][1] = temp;
}
void dijkstras(int source, int use)
{
priority_queue<pair<int, ll>, vector<pair<int, ll> >, greater<pair<int, ll> > > points; //first one is the id, second is the distance from source
for (int i=0; i<n; i++)
{
dist[i][use] = LLONG_MAX;
}
dist[source][use] = 0;
points.push(make_pair(source, 0));
while (points.size())
{
pair<int, ll> temp = points.top();
points.pop();
ll cdist = temp.second;
int id = temp.first;
// if (use == 2)
// {
// cerr << id << " " << cdist << endl;
// // if (id == 2)
// // {
// // cerr << cdist << endl; //for some reason this becomes -1294967296
// // cerr << dist[id][use] << endl;
// // }
// }
if (cdist != dist[id][use])
{
continue;
}
for (auto k: adj[id])
{
// if (use == 2)
// {
// cerr << id << ": " << k.first << endl;
// // cerr << dist[k.first][use] << endl;
// // cerr << cdist + k.second << endl;
// // cerr << endl;
// }
if (dist[k.first][use] > cdist + k.second)
{
// if (use == 2)
// {
// cerr << id << ": " << k.first << endl;
// // cerr << dist[k.first][use] << endl;
// // cerr << cdist + k.second << endl;
// // cerr << endl;
// }
dist[k.first][use] = cdist + k.second;
if (use == 0)
{
parents[k.first].clear();
parents[k.first].push_back(id);
}
// if (use == 2 && k.first == 2)
// {
// cerr << dist[k.first][use] << endl; //this is still 3000000000
// }
points.push(make_pair(k.first, dist[k.first][use]));
}
else if (use == 0 && dist[k.first][use] == cdist + k.second)
{
parents[k.first].push_back(id);
//we won't push this back into the queue because if the thing is not infinity, that the last time that it was reduced
// it was already pushed into the priority queue, meaning that another update with still the same distance is meaningless
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
//freopen("joi.in", "r", stdin);
//freopen("joi.out", "w", stdout);
cin >> n >> m >> s >> t >> u >> v;
s--;
t--;
u--;
v--;
for (int i=0; i<m; i++)
{
int a, b, c;
cin >> a >> b >> c;
a--;
b--;
adj[a].push_back(make_pair(b,c));
adj[b].push_back(make_pair(a,c));
}
//let's first see that we've read everything in correctly
dijkstras(s, 0);
//then check that we're doing the dijkstras correctly from source s
dijkstras(u, 1);
dijkstras(v, 2);
//cerr << dist[t][2] << endl;
//then check that we're getting the right dijkstras from u and v
//we should probably assemble the lowest path tree
queue<int> stuff;
stuff.push(t);
vis[t] = true;
dagnodes.push_back(t);
while (stuff.size())
{
int cur = stuff.front();
stuff.pop();
for (int i=0; i<parents[cur].size(); i++)
{
int k = parents[cur][i];
shortpathchildren[k].push_back(cur);
if (!vis[k])
{
dagnodes.push_back(k);
stuff.push(k);
vis[k] = true;
}
}
}
//then we should check that the dagnodes and children are correct
for (auto k: dagnodes)
{
dpU[k][0] = LLONG_MAX;
dpV[k][0] = LLONG_MAX;
}
ll minlengthone = LLONG_MAX;
for (auto k: dagnodes)
{
// ll x = dpUfuncone(k);
// ll y = dpVfuncone(k);
// cerr << "from node " << k << ", we get " << x << " " << y << endl;
minlengthone = min(minlengthone, dpUfuncone(k) + dpVfuncone(k));
// if (dpUfuncone(k) + dpVfuncone(k) < 0)
// {
// cerr << k << endl;
// }
}
//then we check the dp process
for (auto k: dagnodes)
{
dpU[k][1] = LLONG_MAX;
dpV[k][1] = LLONG_MAX;
}
ll minlengthtwo = LLONG_MAX;
for (auto k: dagnodes)
{
minlengthtwo = min(minlengthtwo, dpUfunctwo(k) + dpVfunctwo(k));
}
//then we check the second dp process
// cerr << dist[u][2] << endl;
// cerr << minlengthone << endl;
// cerr << minlengthtwo << endl;
// cerr << LLONG_MIN << endl;
//how did both become LL_ONG_MIN? this must mean that dpUfunc and dpVfunc returned LLONG_MIN, but what?
cout << min(dist[u][2], min(minlengthone, minlengthtwo)) << endl;
}
Compilation message
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:198:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
198 | for (int i=0; i<parents[cur].size(); i++)
| ~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2100 ms |
51220 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2068 ms |
42320 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2060 ms |
9088 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2100 ms |
51220 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
