#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 100005
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;
for(ll i = 0; i < g[node].size(); i++){
ll coc = g[node][i].st;
ll uz = g[node][i].nd;
if(dp[o][node] + uz < dp[o][coc]){
dp[o][coc] = dp[o][node] + uz;
if(!us[coc])
p.push(mp(-(dp[o][coc]) , 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 +s 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];
// }
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();
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[node] + uz < en[coc]){
en[coc] = en[node] + uz;
cvp[coc] = ymn0 + ymn1;
if(!us[coc])
p.push( mp( mp( -(en[coc]), coc ) , mp( ymn0 , ymn1 ) ) );
}
if(en[node] + uz == en[coc]){
cvp[coc] = min(cvp[coc], ymn0 + ymn1);
if(!us[coc])
p.push( mp( mp( -(en[coc]), 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:29: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:105:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ll i = 0; i < g[node].size(); i++){
~~^~~~~~~~~~~~~~~~
commuter_pass.cpp:97:6: warning: unused variable 'yol' [-Wunused-variable]
ll yol = -p.top().st.st;
^~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:133: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:136: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 |
1810 ms |
82876 KB |
Output is correct |
| 2 |
Execution timed out |
2064 ms |
263168 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2051 ms |
263168 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1658 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 |
1810 ms |
82876 KB |
Output is correct |
| 2 |
Execution timed out |
2064 ms |
263168 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
