이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <unordered_set>
#include <cstring>
#define int long long
using namespace std;
vector<tuple<int, int, int>> graf[100005];
unordered_set<int> vs[200005];
int raz[100005];
int raz1[100005];
vector<pair<int, int>> pr[100005];
int oz = 1;
int start = 0;
void oznaci(int u)
{
bool prv = 1;
for (auto [v, i] : pr[u])
{
if (!prv)
oz++;
vs[i].insert(oz);
oznaci(v);
prv = 0;
}
}
int32_t main()
{
int n, m;
cin >> n >> m;
int s, t;
cin >> s >> t;
start = s;
int zc, kn;
cin >> zc >> kn;
for (int i = 0; i < m; i++)
{
int u, v, w;
cin >> u >> v >> w;
graf[u].push_back({v, w, i});
graf[v].push_back({u, w, i});
}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
raz[s] = -1;
pq.push({0, s});
while (!pq.empty())
{
auto [d, u] = pq.top();
pq.pop();
if (d > raz[u] && raz[u] != -1)
continue;
for (auto [v, w, i] : graf[u])
{
if (raz[v] && raz[v] < d+w)
continue;
if (d+w < raz[v])
pr[v].clear();
pr[v].push_back({u, i});
raz[v] = d+w;
pq.push({raz[v], v});
}
}
oznaci(t);
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq1;
for (int to = 1; to <= oz; to++)
pq1.push({0, zc, to});
memset(raz1, -1, sizeof(raz1));
raz1[zc] = 0;
while (!pq1.empty())
{
auto [d, u, zs] = pq1.top();
// cout<< u << " " << d << "\n";
pq1.pop();
if (d > raz1[u] && raz1[u])
continue;
if (u == kn)
{
cout << d << "\n";
exit(0);
}
for (auto [v, w, i] : graf[u])
{
int ns = d;
// if (v == 4 && u == 2)
// cout << d << " " << zs << " " << w << " " << (vs[i].find(zs) == vs[i].end()) << "\n";
if (vs[i].find(zs) == vs[i].end())
ns+=w;
if ((raz1[v] != -1 && raz1[v] < ns) || (raz1[v] == d))
continue;
// if (u == 3 && v == 2)
// cout << raz1[v] << " " << ns << " " << d << "\n";
// cout << "-> " << v << "\n";
raz1[v] = ns;
pq1.push({raz1[v], v, zs});
}
}
cout << "error\n";
exit(0);
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
commuter_pass.cpp: In function 'void oznaci(long long int)':
commuter_pass.cpp:23:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
23 | for (auto [v, i] : pr[u])
| ^
commuter_pass.cpp: In function 'int32_t main()':
commuter_pass.cpp:54:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
54 | auto [d, u] = pq.top();
| ^
commuter_pass.cpp:58:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
58 | for (auto [v, w, i] : graf[u])
| ^
commuter_pass.cpp:77:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
77 | auto [d, u, zs] = pq1.top();
| ^
commuter_pass.cpp:87:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
87 | for (auto [v, w, i] : 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... |