#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
int n, m;
int s, t, u, v;
vector<vector<pair<int, long long>>> adj;
vector<vector<int>> p;
vector<bool> visited;
vector<bool> on_path;
vector<bool> processed;
void dfs(int cur) {
if (processed[cur])
return;
on_path[cur] = true;
processed[cur] = true;
for (auto x : p[cur]) {
dfs(x);
}
}
void dijkstras(vector<vector<int>> &parent, vector<long long> &dist, int start) {
priority_queue<pair<long long, int>> pq;
pq.push({0, start});
while (!pq.empty()) {
int x = pq.top().second;
pq.pop();
if (visited[x])
continue;
visited[x] = true;
for (auto e : adj[x]) {
long long w = e.second;
if (w + dist[x] < dist[e.first]) {
parent[e.first].clear();
parent[e.first].push_back(x);
dist[e.first] = dist[x]+w;
pq.push({-dist[e.first], e.first});
}
else if (w + dist[x] == dist[e.first]) {
parent[e.first].push_back(x);
}
}
}
}
int main() {
cin >> n >> m;
adj.resize(n+1);
p.resize(n+1);
processed.resize(n+1);
on_path.resize(n+1);
visited.resize(n+1);
cin >> s >> t >> u >> v;
for (int i = 0; i < m; i++) {
int x, y;
long long w;
cin >> x >> y >> w;
adj[x].push_back({y, w});
adj[y].push_back({x, w});
}
p[s].push_back(s);
vector<long long> d(n+1, INF);
d[s] = 0;
dijkstras(p, d, s);
for (auto x : p[t]) {
dfs(x);
}
on_path[t] = true;
vector<vector<int>> temp(n+1);
vector<long long> dv(n+1, INF);
dv[v] = 0;
fill(visited.begin(), visited.end(), false);
dijkstras(temp, dv, v);
long long ans = INF;
long long mnv = INF;
for (int i = 1; i <= n; i++) {
if (!on_path[i])
continue;
mnv = min(mnv, dv[i]);
ans = min(ans, mnv);
}
cout << ans << '\n';
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
284 ms |
26580 KB |
Output is correct |
2 |
Correct |
287 ms |
25988 KB |
Output is correct |
3 |
Correct |
262 ms |
27552 KB |
Output is correct |
4 |
Correct |
281 ms |
26408 KB |
Output is correct |
5 |
Correct |
301 ms |
29184 KB |
Output is correct |
6 |
Correct |
294 ms |
30224 KB |
Output is correct |
7 |
Correct |
279 ms |
29328 KB |
Output is correct |
8 |
Correct |
291 ms |
29168 KB |
Output is correct |
9 |
Correct |
291 ms |
30104 KB |
Output is correct |
10 |
Correct |
254 ms |
29948 KB |
Output is correct |
11 |
Correct |
123 ms |
23444 KB |
Output is correct |
12 |
Correct |
297 ms |
30236 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
300 ms |
26716 KB |
Output is correct |
2 |
Correct |
302 ms |
27008 KB |
Output is correct |
3 |
Incorrect |
280 ms |
26480 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
1624 KB |
Output is correct |
2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
284 ms |
26580 KB |
Output is correct |
2 |
Correct |
287 ms |
25988 KB |
Output is correct |
3 |
Correct |
262 ms |
27552 KB |
Output is correct |
4 |
Correct |
281 ms |
26408 KB |
Output is correct |
5 |
Correct |
301 ms |
29184 KB |
Output is correct |
6 |
Correct |
294 ms |
30224 KB |
Output is correct |
7 |
Correct |
279 ms |
29328 KB |
Output is correct |
8 |
Correct |
291 ms |
29168 KB |
Output is correct |
9 |
Correct |
291 ms |
30104 KB |
Output is correct |
10 |
Correct |
254 ms |
29948 KB |
Output is correct |
11 |
Correct |
123 ms |
23444 KB |
Output is correct |
12 |
Correct |
297 ms |
30236 KB |
Output is correct |
13 |
Correct |
300 ms |
26716 KB |
Output is correct |
14 |
Correct |
302 ms |
27008 KB |
Output is correct |
15 |
Incorrect |
280 ms |
26480 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |