#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> ii;
ll n, m, s, t, u, v, a, b, c;
vector<ii> adj[100005];
ll dist_s[100005], dist_t[100005], dist_u[100005], dist_v[100005];
ll visited[2][100005];
ll mini[2][100005];
priority_queue<ii> pq;
void dij(ll *dist, ll node){
pq.push(make_pair(0, node)); ///dist, node
dist[node] = 0;
//printf("\n");
while (!pq.empty()){
ii now = pq.top();
pq.pop();
//printf("%lld %lld\n", now.first, now.second);
if (now.first == dist[now.second]){
for (ii neigh: adj[now.second]){
if (neigh.second + dist[now.second] < dist[neigh.first]){
dist[neigh.first] = neigh.second + dist[now.second];
pq.push(make_pair(dist[neigh.first], neigh.first));
}
}
}
}
}
ll dfs_s(ll node){
if (visited[0][node] == 1) return mini[0][node];
visited[0][node] = 1;
if (node == s){
mini[0][s] = dist_u[s];
return dist_u[s];
}
ll low = dist_u[node];
for (ii neigh:adj[node]){
if (visited[0][neigh.first] == 1) continue;
if (dist_s[neigh.first] + neigh.second == dist_s[node]){
ll posmin = dfs_s(neigh.first);
low = min(low, posmin);
}
}
mini[0][node] = low;
return mini[0][node];
}
ll dfs_t(ll node){
if (visited[1][node] == 1) return mini[1][node];
visited[1][node] = 1;
if (node == t){
mini[1][t] = dist_u[t];
return dist_u[t];
}
ll low = dist_u[node];
for (ii neigh:adj[node]){
if (visited[1][neigh.first] == 1) continue;
if (dist_t[neigh.first] + neigh.second == dist_t[node]){
ll posmin = dfs_t(neigh.first);
low = min(low, posmin);
}
}
mini[1][node] = low;
return mini[1][node];
}
int main(){
scanf("%lld%lld", &n, &m);
scanf("%lld%lld", &s, &t);
scanf("%lld%lld", &u, &v);
for (ll i = 0; i <= n; ++i){
dist_s[i] = 1023456789102345;
dist_t[i] = 1023456789102345;
dist_u[i] = 1023456789102345;
dist_v[i] = 1023456789102345;
mini[0][i] = 1023456789102345;
mini[1][i] = 1023456789102345;
}
for (ll i = 0; i < m; ++i){
scanf("%lld%lld%lld", &a, &b, &c);
adj[a].push_back(make_pair(b,c));
adj[b].push_back(make_pair(a,c));
}
dij(dist_s, s);
dij(dist_t, t);
dij(dist_u, u);
dij(dist_v, v);
dfs_s(t);
dfs_t(s);
ll out = dist_u[v];
for (ll i = 1; i <= n; ++i){
out = min(out, mini[0][i] + dist_v[i]);
out = min(out, mini[1][i] + dist_v[i]);
//printf("%lld %lld %lld %lld %lld %lld %lld\n", i, dist_s[i], dist_t[i], dist_u[i], dist_v[i], mini[0][i], mini[1][i]);
}
printf("%lld", out);
return 0;
}
Compilation message
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
73 | scanf("%lld%lld", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
74 | scanf("%lld%lld", &s, &t);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
75 | scanf("%lld%lld", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:85:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
85 | scanf("%lld%lld%lld", &a, &b, &c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2098 ms |
19060 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2055 ms |
19188 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
4224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2098 ms |
19060 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
