이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define ll long long
#define li pair <ll, int>
const int N = 1e5 + 10;
int n, m, x, y;
int a, b, c, d;
ll cost, A[N], B[N], C[N], D[N];
vector <li> v[N];
void dijkstra(int st, ll dis[]) {
fill_n(dis, n + 1, 1e17);
dis[st] = 0;
priority_queue < li, vector <li>, greater <li> > q;
q.push(li(0, st));
while (!q.empty()) {
li p = q.top(); q.pop();
int u = p.second;
ll w = p.first;
if (w > dis[u]) continue;
for (li z: v[u]) {
if (z.first + w < dis[z.second]) {
dis[z.second] = z.first + w;
q.push(li(dis[z.second], z.second));
}
}
}
}
void pre() {
dijkstra(a, A);
dijkstra(b, B);
dijkstra(c, C);
dijkstra(d, D);
}
ll best = 1e17;
ll dp[2][N];
bool vis[N];
void dfs(int s, int p) {
vis[s] = true;
dp[0][s] = dp[1][s] = 1e17;
for (li z: v[s]) {
if (A[s] + z.first + B[z.second] == A[b]) {
if (z.second == p) continue;
if (!vis[z.second]) dfs(z.second, s);
dp[0][s] = min(dp[0][z.second], dp[0][s]);
dp[1][s] = min(dp[1][z.second], dp[1][s]);
}
}
best = min(best, dp[0][s] + C[s]);
best = min(best, dp[1][s] + D[s]);
dp[0][s] = min(dp[0][s], D[s]);
dp[1][s] = min(dp[1][s], C[s]);
}
void solve() {
best = C[d];
dfs(a, -1);
cout << best << "\n";
}
int main() {
cin.tie(nullptr);
cout.tie(nullptr);
ios_base::sync_with_stdio(false);
cin >> n >> m;
cin >> a >> b >> c >> d;
while (m--) {
cin >> x >> y >> cost;
v[x].push_back(li(cost, y));
v[y].push_back(li(cost, x));
}
pre();
solve();
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... |