This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <queue>
#include <set>
using namespace std;
using ll = long long;
#define int ll
#define fore(a, b, c) for(int a=b; a<c; ++a)
#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()
#define vi vector<int>
#define ii pair<int,int>
#define F first
#define S second
const int MAXN = 1010;
vector<ii> adj[MAXN];
int n, m, s, t, u, v;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
cin >> s >> t;
cin >> u >> v;
vector<vi> d(n+1, vi(n+1, 4e18));
fore(i, 0, m){
int x, y, c;
cin >> x >> y >> c;
adj[x].push_back({y, c});
adj[y].push_back({x, c});
d[x][y] = d[y][x] = c;
}
fore(i, 1, n+1){
d[i][i] = 0;
}
auto dijkstra = [&](int r, vi &dis) -> void {
dis[r] = 0;
priority_queue<ii, vector<ii>, greater<ii>> pq;
pq.push({0, r});
while(sz(pq)){
auto [cost, node] = pq.top();
pq.pop();
if(cost != dis[node]) continue;
for(auto [to, c] : adj[node]){
if(dis[node] + c < dis[to]){
dis[to] = dis[node] + c;
pq.push({dis[to], to});
}
}
}
};
// fore(i, 1, n+1){
// dijkstra(i, d[i]);
// }
// floyd-warshal
fore(k, 1, n+1){
fore(i, 1, n+1){
fore(j, 1, n+1){
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
int ans = d[u][v];
fore(xx, 1, n+1){
fore(yy, 1, n+1){
int x = xx, y = yy;
if(d[s][y] < d[s][x]) swap(x, y);
if(d[s][x] + d[x][y] != d[s][y]) continue;
if(d[s][x] + d[x][y] + d[y][t] != d[s][t]) continue;
int res = min(d[u][x] + d[v][y], d[v][x] + d[u][y]);
ans = min(ans, res);
}
}
cout << ans;
}
Compilation message (stderr)
commuter_pass.cpp: In lambda function:
commuter_pass.cpp:56:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
56 | auto [cost, node] = pq.top();
| ^
commuter_pass.cpp:61:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
61 | for(auto [to, c] : adj[node]){
| ^
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:51:10: warning: variable 'dijkstra' set but not used [-Wunused-but-set-variable]
51 | auto dijkstra = [&](int r, vi &dis) -> void {
| ^~~~~~~~
# | 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... |