oj.uz

답안 #66795

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
66795 2018-08-12T10:19:58 Z ekrem Commuter Pass (JOI18_commuter_pass) C++
15 / 100
 681 ms 24032 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], dp[2][N];
ii cvp[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] = mp(ymn0 , ymn1);
				if(!us[coc])
					p.push( mp(  mp( -(en[coc]), coc )  ,  mp( ymn0 , ymn1 )  ) );
			}
			if(en[node] + uz == en[coc]){
				if(ymn0 + ymn1 < cvp[coc].st + cvp[coc].nd)
					cvp[coc] = mp(ymn0 , ymn1);

			}
		}
	}
	ans = cvp[hed].st + cvp[hed].nd;
}

int main() {
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);

	for(ll i = 0; i < N; i++)
		cvp[i].st = cvp[i].nd = 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:24:6: warning: unused variable 'yol' [-Wunused-variable]
   ll yol = -p.top().st;
      ^~~
commuter_pass.cpp: In function 'void bitir(ll, ll)':
commuter_pass.cpp:106:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(ll i = 0; i < g[node].size(); i++){
                 ~~^~~~~~~~~~~~~~~~
commuter_pass.cpp:98:6: warning: unused variable 'yol' [-Wunused-variable]
   ll yol = -p.top().st.st;
      ^~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:134: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:137: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

# 결과 실행 시간 메모리 Grader output
1 Correct 553 ms 24028 KB Output is correct
2 Correct 544 ms 24028 KB Output is correct
3 Correct 599 ms 24028 KB Output is correct
4 Correct 516 ms 24028 KB Output is correct
5 Correct 464 ms 24028 KB Output is correct
6 Correct 597 ms 24032 KB Output is correct
7 Incorrect 515 ms 24032 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 602 ms 24032 KB Output is correct
2 Correct 548 ms 24032 KB Output is correct
3 Correct 631 ms 24032 KB Output is correct
4 Correct 496 ms 24032 KB Output is correct
5 Correct 557 ms 24032 KB Output is correct
6 Correct 600 ms 24032 KB Output is correct
7 Correct 643 ms 24032 KB Output is correct
8 Correct 574 ms 24032 KB Output is correct
9 Correct 681 ms 24032 KB Output is correct
10 Correct 560 ms 24032 KB Output is correct
11 Correct 201 ms 24032 KB Output is correct
12 Correct 522 ms 24032 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 20 ms 24032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 553 ms 24028 KB Output is correct
2 Correct 544 ms 24028 KB Output is correct
3 Correct 599 ms 24028 KB Output is correct
4 Correct 516 ms 24028 KB Output is correct
5 Correct 464 ms 24028 KB Output is correct
6 Correct 597 ms 24032 KB Output is correct
7 Incorrect 515 ms 24032 KB Output isn't correct
8 Halted 0 ms 0 KB -