이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+1;
int n;
vector< pair<long long, int> > a[maxn];
vector<long long> dijkstra(int start)
{
vector<long long> d(n+1, 1e16);
d[start] = 0;
priority_queue< pair<long long, int> > q;
q.push(make_pair(0, start));
vector<bool> vs(n+1);
while (q.size())
{
int u = q.top().second;
q.pop();
if (vs[u]) continue;
vs[u] = 1;
for (int i = 0; i < (int)a[u].size(); i++)
{
int v = a[u][i].first, w = a[u][i].second;
if (d[u]+w < d[v])
{
d[v] = d[u]+w;
q.push(make_pair(-d[v], v));
}
}
}
return d;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int m, s, t, u, v;
cin >> n >> m >> s >> t >> u >> v;
for (int i = 1; i <= m; i++)
{
int u, v, w;
cin >> u >> v >> w;
a[u].push_back(make_pair(v, w));
a[v].push_back(make_pair(u, w));
}
if (s == u)
{
long long ans = 1e16;
vector<long long> ds, dt, dv;
ds = dijkstra(s), dt = dijkstra(t), dv = dijkstra(v);
for (int i = 1; i <= n; i++)
if (ds[i]+dt[i] == ds[t]) ans = min(ans, dv[i]);
cout << ans;
return 0;
}
vector< vector<long long> > d(n+1, vector<long long> (n+1, 1e16));
for (int i = 1; i <= n; i++)
{
d[i][i] = 0;
for (int j = 0; j < (int)a[i].size(); j++)
d[i][a[i][j].first] = a[i][j].second;
}
for (int k = 1; k <= n; k++)
for (int u = 1; u <= n; u++)
for (int v = 1; v <= n; v++)
d[u][v] = min(d[u][v], d[u][k]+d[k][v]);
long long ans = 1e16;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (d[s][i]+d[i][j]+d[j][t] == d[s][t])
ans = min(ans, d[u][i]+d[j][v]);
cout << ans;
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... |