#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;
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);
if (zc > 10)
exit(-1);
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 (vs[i].empty() || vs[i].find(zs) == vs[i].end())
ns+=w;
if ((raz1[v] != -1 && raz1[v] < ns) || (raz1[v] == d))
continue;
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:25:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
25 | for (auto [v, i] : pr[u])
| ^
commuter_pass.cpp: In function 'int32_t main()':
commuter_pass.cpp:56:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
56 | auto [d, u] = pq.top();
| ^
commuter_pass.cpp:60:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
60 | 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 |
Runtime error |
276 ms |
40636 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
264 ms |
46280 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
466 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
276 ms |
40636 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
