#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define FOR(i, a, b) for (int i = a; i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define F0R1(i, a) for (int i = 1; i <= (a); i++)
#define FORd(i, a, b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i, a) for (int i = (a)-1; i >= 0; i--)
#define F0Rd1(i, a) for (int i = a; i > 0; i--)
#define SORT(vec) sort(vec.begin(), vec.end())
#define S0RT(arr, n) sort(arr, arr + n)
#define pA first
#define pB second
#define MOD 1000000007
#define nl "\n"
#define pb push_back
int n, m, s, t, u, v;
class cmp {
public:
bool operator()(vector<int> a, vector<int> b) { return a[1] > b[1]; }
};
int dist[100000];
vector<pii> adj[100000];
bool inPass[100000];
unordered_set<int> prevs[100000];
void dijkstra(int root) { // traceback
for (int i = 0; i < n; i++) {
dist[i] = 1e9;
}
dist[root] = 0;
priority_queue<vector<int>, vector<vector<int>>, cmp> nodes;
nodes.push({root, 0, -1});
while (!nodes.empty()) {
int node = nodes.top()[0];
int minDist = nodes.top()[1];
int parent = nodes.top()[2];
nodes.pop();
if (node == t) {
return;
}
if (minDist != dist[node]) {
continue;
}
for (pii i : adj[node]) {
int neighbor = i.pA;
int length = i.pB;
if (dist[node] + length < dist[neighbor]) {
dist[neighbor] = dist[node] + length;
nodes.push({neighbor, dist[neighbor], node});
prevs[neighbor].insert(node);
} else if (dist[node] + length == dist[neighbor]) {
prevs[neighbor].insert(node);
}
}
}
}
bool vis[100000];
void dfs(int node) {
inPass[node] = true;
vis[node] = true;
for (int i : prevs[node]) {
if (!vis[i]) {
dfs(i);
}
}
}
int distU[100000];
int dijkstraU(int root) { // traceback
for (int i = 0; i < n; i++) {
distU[i] = 1e9;
}
distU[root] = 0;
priority_queue<vector<int>, vector<vector<int>>, cmp> nodes;
nodes.push({root, 0, -1});
while (!nodes.empty()) {
int node = nodes.top()[0];
int minDist = nodes.top()[1];
int parent = nodes.top()[2];
nodes.pop();
if (inPass[node]) {
return minDist;
}
if (minDist != distU[node]) {
continue;
}
for (pii i : adj[node]) {
int neighbor = i.pA;
int length = i.pB;
if (distU[node] + length < distU[neighbor]) {
distU[neighbor] = distU[node] + length;
nodes.push({neighbor, distU[neighbor], node});
}
}
}
}
int distV[100000];
int dijkstraV(int root) { // traceback
for (int i = 0; i < n; i++) {
distV[i] = 1e9;
}
distV[root] = 0;
priority_queue<vector<int>, vector<vector<int>>, cmp> nodes;
nodes.push({root, 0, -1});
while (!nodes.empty()) {
int node = nodes.top()[0];
int minDist = nodes.top()[1];
int parent = nodes.top()[2];
nodes.pop();
if (inPass[node]) {
return minDist;
}
if (minDist != distV[node]) {
continue;
}
for (pii i : adj[node]) {
int neighbor = i.pA;
int length = i.pB;
if (distV[node] + length < distV[neighbor]) {
distV[neighbor] = distV[node] + length;
nodes.push({neighbor, distV[neighbor], node});
}
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> s >> t >> u >> v;
s--;
t--;
u--;
v--;
// go through and mark every node in shortest paths from S to T as part of the shortest path, since
// you'll never use more than 1 distinct shortest path going from U to V, as when you switch from one
// shortest path to another you're simply creating a new shortest path
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
a--;
b--;
adj[a].pb(pii(b, c));
adj[b].pb(pii(a, c));
}
dijkstra(s);
dfs(t);
cout << min(dijkstraU(u) + dijkstraV(v), distU[v]) << nl;
}
Compilation message
commuter_pass.cpp: In function 'void dijkstra(int)':
commuter_pass.cpp:44:7: warning: unused variable 'parent' [-Wunused-variable]
44 | int parent = nodes.top()[2];
| ^~~~~~
commuter_pass.cpp: In function 'int dijkstraU(int)':
commuter_pass.cpp:90:7: warning: unused variable 'parent' [-Wunused-variable]
90 | int parent = nodes.top()[2];
| ^~~~~~
commuter_pass.cpp: In function 'int dijkstraV(int)':
commuter_pass.cpp:121:7: warning: unused variable 'parent' [-Wunused-variable]
121 | int parent = nodes.top()[2];
| ^~~~~~
commuter_pass.cpp: In function 'int dijkstraU(int)':
commuter_pass.cpp:85:56: warning: control reaches end of non-void function [-Wreturn-type]
85 | priority_queue<vector<int>, vector<vector<int>>, cmp> nodes;
| ^~~~~
commuter_pass.cpp: In function 'int dijkstraV(int)':
commuter_pass.cpp:116:56: warning: control reaches end of non-void function [-Wreturn-type]
116 | priority_queue<vector<int>, vector<vector<int>>, cmp> nodes;
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
312 ms |
36980 KB |
Output is correct |
| 2 |
Correct |
358 ms |
37616 KB |
Output is correct |
| 3 |
Incorrect |
409 ms |
35876 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
297 ms |
34984 KB |
Output is correct |
| 2 |
Correct |
377 ms |
36104 KB |
Output is correct |
| 3 |
Correct |
442 ms |
35612 KB |
Output is correct |
| 4 |
Correct |
311 ms |
34648 KB |
Output is correct |
| 5 |
Correct |
360 ms |
35760 KB |
Output is correct |
| 6 |
Incorrect |
453 ms |
35872 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
9580 KB |
Output is correct |
| 2 |
Runtime error |
11 ms |
16460 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
312 ms |
36980 KB |
Output is correct |
| 2 |
Correct |
358 ms |
37616 KB |
Output is correct |
| 3 |
Incorrect |
409 ms |
35876 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
