#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, int gl)
{
if (u == start)
return;
if (gl > 200005)
exit(-1);
bool prv = 1;
for (auto [v, i] : pr[u])
{
if (!prv)
oz++;
vs[i].insert(oz);
oznaci(v, gl+1);
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, 0);
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].empty() || 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;
}
Compilation message
commuter_pass.cpp: In function 'void oznaci(long long int, long long int)':
commuter_pass.cpp:27:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
27 | for (auto [v, i] : pr[u])
| ^
commuter_pass.cpp: In function 'int32_t main()':
commuter_pass.cpp:58:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
58 | auto [d, u] = pq.top();
| ^
commuter_pass.cpp:62:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
62 | for (auto [v, w, i] : graf[u])
| ^
commuter_pass.cpp:81:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
81 | auto [d, u, zs] = pq1.top();
| ^
commuter_pass.cpp:91:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
91 | for (auto [v, w, i] : graf[u])
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
306 ms |
43764 KB |
Output is correct |
2 |
Runtime error |
752 ms |
262144 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
258 ms |
45456 KB |
Output is correct |
2 |
Correct |
313 ms |
47876 KB |
Output is correct |
3 |
Correct |
317 ms |
46344 KB |
Output is correct |
4 |
Correct |
288 ms |
47976 KB |
Output is correct |
5 |
Correct |
326 ms |
49416 KB |
Output is correct |
6 |
Correct |
358 ms |
55516 KB |
Output is correct |
7 |
Correct |
307 ms |
57284 KB |
Output is correct |
8 |
Correct |
345 ms |
48312 KB |
Output is correct |
9 |
Correct |
284 ms |
49348 KB |
Output is correct |
10 |
Correct |
261 ms |
45372 KB |
Output is correct |
11 |
Correct |
158 ms |
44880 KB |
Output is correct |
12 |
Correct |
378 ms |
56064 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
389 ms |
262144 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
306 ms |
43764 KB |
Output is correct |
2 |
Runtime error |
752 ms |
262144 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |