#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define heap priority_queue
#define inf 1000000000000000007
#define N 1000005
using namespace std;
typedef long long ll;
typedef pair < ll , ll > ii;
ll n, m, s, t, u, v, ans, us[N], en[N], cvp[N], dp[2][N];
vector < ii > g[N];
void bul(ll o, ll sr){
memset(us, 0, sizeof us);
heap < ii > p;
p.push(mp(0, sr));
dp[o][sr] = 0;
while(!p.empty()){
ll yol = -p.top().st;
ll node = p.top().nd;
p.pop();
us[node] = 1;
// cout << node << endl;
for(ll i = 0; i < g[node].size(); i++){
ll coc = g[node][i].st;
ll uz = g[node][i].nd;
dp[o][coc] = min(dp[o][coc], dp[o][node] + uz);
if(!us[coc])
p.push(mp(-(dp[o][node] + uz) , coc ));
}
}
// if(o == 1)
// for(ll i = 1; i <= n; i++)
// cout << i << " -> " << dp[!o][i] << " , " << dp[o][i] << endl;
}
void bitir(ll sr, ll hed){
memset(us, 0, sizeof us);
heap < pair < ii , ii > > p;
p.push( mp( mp( 0, sr ) , mp( dp[0][sr] , dp[1][sr] ) ) );
en[sr] = 0;
while(!p.empty()){
ll yol = -p.top().st.st;
ll node = p.top().st.nd;
ll mn0 = p.top().nd.st;
ll mn1 = p.top().nd.nd;
p.pop();
// cout << yol << " -> " << node << " -> " << mn0 << " " << mn1 << endl;
// mn0 = min(mn0, dp[0][node]);
// mn1 = min(mn1, dp[1][node]);
// if(node = hed)
// ans = min(ans, mn0 + mn1);
us[node] = 1;
for(ll i = 0; i < g[node].size(); i++){
ll coc = g[node][i].st;
ll uz = g[node][i].nd;
ll ymn0 = min(mn0 , dp[0][coc]);
ll ymn1 = min(mn1 , dp[1][coc]);
if(en[coc] > en[node] + uz){
en[coc] = en[node] + uz;
cvp[coc] = ymn0 + ymn1;
}
if(en[coc] == en[node] + uz){
en[coc] = en[node] + uz;
cvp[coc] = min(cvp[coc], ymn0 + ymn1);
if(us[coc]){
// printf("%lld nodundan %lld cocuguna %lld %lld minleriyle gidiyoz\n",node,coc,ymn0,ymn1);
p.push( mp( mp( -(yol + uz), coc ) , mp( ymn0 , ymn1 ) ) );
}
}
if(!us[coc]){
// printf("amk %lld nodundan %lld cocuguna %lld %lld minleriyle gidiyoz\n",node,coc,ymn0,ymn1);
p.push( mp( mp( -(yol + uz), coc ) , mp( ymn0 , ymn1 ) ) );
}
}
}
ans = cvp[hed];
}
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
for(ll i = 0; i < N; i++)
ans = en[i] = dp[0][i] = dp[1][i] = inf;
scanf("%lld %lld %lld %lld %lld %lld",&n ,&m ,&s ,&t ,&u ,&v);
for(ll i = 1; i <= m; i++){
ll a, b, c;
scanf("%lld %lld %lld",&a ,&b ,&c);
g[a].pb(mp(b, c));
g[b].pb(mp(a, c));
}
bul(0, u);
bul(1, v);
bitir(s, t);
ans = min(ans, dp[0][v]);
ans = min(ans, dp[1][u]);
printf("%lld\n",ans);
return 0;
}
Compilation message
commuter_pass.cpp: In function 'void bul(ll, ll)':
commuter_pass.cpp:30:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ll i = 0; i < g[node].size(); i++){
~~^~~~~~~~~~~~~~~~
commuter_pass.cpp:23:6: warning: unused variable 'yol' [-Wunused-variable]
ll yol = -p.top().st;
^~~
commuter_pass.cpp: In function 'void bitir(ll, ll)':
commuter_pass.cpp:64:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ll i = 0; i < g[node].size(); i++){
~~^~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:97:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld %lld %lld %lld %lld",&n ,&m ,&s ,&t ,&u ,&v);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:100:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld %lld",&a ,&b ,&c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
831 ms |
78628 KB |
Output is correct |
| 2 |
Execution timed out |
2071 ms |
263168 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2082 ms |
263168 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1899 ms |
263168 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
831 ms |
78628 KB |
Output is correct |
| 2 |
Execution timed out |
2071 ms |
263168 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
