// https://oj.uz/problem/view/JOI18_commuter_pass
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple<ll, ll, vector<ll>> tll;
int main() {
ll N, M, S, T, U, V; cin >> N >> M >> S >> T >> U >> V;
vector<vector<pair<ll, ll>>> adj(N + 1);
for(int i = 0; i < M; i++) {
ll a, b, c; cin >> a >> b >> c;
adj[a].push_back({b, c});
adj[b].push_back({a, c});
}
priority_queue<tll, vector<tll>, greater<tll>> q;
vector<ll> empty; empty.push_back({S});
tll start = make_tuple(0, S, empty);
q.push(start);
vector<vector<ll>> paths;
ll min_cost[N + 1];
for(int i = 1; i <= N; i++) {
min_cost[i] = LLONG_MAX;
}
while(!q.empty()) {
tll curr = q.top();
q.pop();
ll cost = get<0>(curr), u = get<1>(curr);
if(cost > min_cost[u]) continue;
vector<ll> path = get<2>(curr);
if(u == T) paths.push_back(path);
for(pair<ll, ll> p : adj[u]) {
ll v = p.first, new_cost = p.second;
if(min_cost[v] >= cost + new_cost) {
if(v == T) paths.clear();
min_cost[v] = cost + new_cost;
path.push_back(v);
q.push(make_tuple(cost + new_cost, v, path));
path.pop_back();
}
}
}
ll ans = LLONG_MAX;
for(vector<ll> path : paths) {
vector<vector<pair<ll, ll>>> adj2 = adj;
for(int i = 0; i < path.size() - 1; i++) {
for(int j = 0; j < adj2[path[i]].size(); j++) {
if(adj2[path[i]][j].first == path[i + 1]) {
adj2[path[i]][j].second = 0;
}
}
for(int j = 0; j < adj2[path[i + 1]].size(); j++) {
if(adj2[path[i + 1]][j].first == path[i]) {
adj2[path[i + 1]][j].second = 0;
}
}
}
for(int i = 1; i <= N; i++) {
min_cost[i] = LLONG_MAX;
}
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> q2;
q2.push({0, U});
while(!q2.empty()) {
ll cost = q2.top().first, u = q2.top().second;
q2.pop();
if(cost > min_cost[u]) continue;
for(pair<ll, ll> p : adj2[u]) {
ll v = p.first, new_cost = p.second;
if(min_cost[v] > cost + new_cost) {
min_cost[v] = cost + new_cost;
q2.push({cost + new_cost, v});
}
}
}
ans = min(ans, min_cost[V]);
}
cout << ans << '\n';
}
Compilation message
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:50:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int i = 0; i < path.size() - 1; i++) {
| ~~^~~~~~~~~~~~~~~~~
commuter_pass.cpp:51:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for(int j = 0; j < adj2[path[i]].size(); j++) {
| ~~^~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:56:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for(int j = 0; j < adj2[path[i + 1]].size(); j++) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
412 ms |
35056 KB |
Output is correct |
| 2 |
Runtime error |
357 ms |
262148 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
341 ms |
262152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
344 ms |
262148 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
412 ms |
35056 KB |
Output is correct |
| 2 |
Runtime error |
357 ms |
262148 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
