이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define inf 1'000'000'000'000'000
#define int long long
using namespace std;
typedef pair<int, int> ii;
vector<ii> graf[100005];
int du[100005];
int dv[100005];
int ds[100005];
int dp[5][100005];
int rez = 0;
bool ob[100005];
void dijkstra1(int start, int arr[])
{
memset(ob, false, sizeof(ob));
priority_queue<ii, vector<ii>, greater<ii>> pq;
pq.push({0, start});
while (!pq.empty())
{
auto [d, u] = pq.top();
pq.pop();
if (ob[u])
continue;
arr[u] = d;
ob[u] = 1;
for (auto [v, w] : graf[u])
pq.push({d + w, v});
}
}
void dijkstra2(int start, int end)
{
memset(dp, -1, sizeof(dp));
memset(ob, false, sizeof(ob));
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
pq.push({0, start, 0});
dp[0][0] = dp[1][0] = inf;
while (!pq.empty())
{
auto [d, u, par] = pq.top();
pq.pop();
if (!ob[u])
{
ob[u] = 1;
ds[u] = d;
dp[0][u] = min(du[u], dp[0][par]);
dp[1][u] = min(dv[u], dp[1][par]);
for (auto [v, w] : graf[u])
pq.push({d + w, v, u});
}
else if (d == ds[u])
{
if (min(du[u], dp[0][par]) + min(dv[u], dp[1][par]) <= dp[0][u] + dp[1][u])
{
dp[0][u] = min(du[u], dp[0][par]);
dp[1][u] = min(dv[u], dp[1][par]);
}
}
}
rez = min(rez, dp[0][end] + dp[1][end]);
}
int32_t main()
{
int n, m, s, t, u, v;
cin >> n >> m >> s >> t >> u >> v;
for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
graf[a].push_back({b, c});
graf[b].push_back({a, c});
}
dijkstra1(u, du);
dijkstra1(v, dv);
rez = du[v];
dijkstra2(s, t);
dijkstra2(t, s);
cout << rez << '\n';
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
commuter_pass.cpp: In function 'void dijkstra1(long long int, long long int*)':
commuter_pass.cpp:25:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
25 | auto [d, u] = pq.top();
| ^
commuter_pass.cpp:31:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
31 | for (auto [v, w] : graf[u])
| ^
commuter_pass.cpp: In function 'void dijkstra2(long long int, long long int)':
commuter_pass.cpp:45:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
45 | auto [d, u, par] = pq.top();
| ^
commuter_pass.cpp:53:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
53 | for (auto [v, w] : graf[u])
| ^
# | 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... |