Submission #66773

#	Time	Username	Problem	Language	Result	Execution time	Memory
66773		ekrem	Commuter Pass (JOI18_commuter_pass)	C++98	0 / 100	2082 ms	263168 KiB

commuter_pass

#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 (stderr)

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);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 16
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45