#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];
}
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:65: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:98: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:101: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);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
571 ms |
25312 KB |
Output is correct |
2 |
Execution timed out |
2047 ms |
263168 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
659 ms |
263168 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1726 ms |
263168 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
571 ms |
25312 KB |
Output is correct |
2 |
Execution timed out |
2047 ms |
263168 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |