oj.uz

Submission #66787

# Submission time Handle Problem Language Result Execution time Memory
66787 2018-08-12T10:12:06 Z ekrem Commuter Pass (JOI18_commuter_pass) C++
15 / 100
 658 ms 23408 KB 
#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);

			}
		}
	}
	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:132: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:135: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);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 576 ms 23132 KB Output is correct
2 Correct 658 ms 23132 KB Output is correct
3 Correct 622 ms 23132 KB Output is correct
4 Correct 609 ms 23132 KB Output is correct
5 Correct 495 ms 23132 KB Output is correct
6 Correct 515 ms 23408 KB Output is correct
7 Incorrect 587 ms 23408 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 593 ms 23408 KB Output is correct
2 Correct 615 ms 23408 KB Output is correct
3 Correct 620 ms 23408 KB Output is correct
4 Correct 476 ms 23408 KB Output is correct
5 Correct 544 ms 23408 KB Output is correct
6 Correct 460 ms 23408 KB Output is correct
7 Correct 529 ms 23408 KB Output is correct
8 Correct 620 ms 23408 KB Output is correct
9 Correct 544 ms 23408 KB Output is correct
10 Correct 543 ms 23408 KB Output is correct
11 Correct 216 ms 23408 KB Output is correct
12 Correct 477 ms 23408 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 23408 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 576 ms 23132 KB Output is correct
2 Correct 658 ms 23132 KB Output is correct
3 Correct 622 ms 23132 KB Output is correct
4 Correct 609 ms 23132 KB Output is correct
5 Correct 495 ms 23132 KB Output is correct
6 Correct 515 ms 23408 KB Output is correct
7 Incorrect 587 ms 23408 KB Output isn't correct
8 Halted 0 ms 0 KB -