Submission #66806

#	Time	Username	Problem	Language	Result	Execution time	Memory
66806		ekrem	Commuter Pass (JOI18_commuter_pass)	C++98	100 / 100	625 ms	22740 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 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 < ii > p;
	p.push(mp(0, sr));
	en[sr] = 0;
	cvp[sr].st = dp[0][sr];
	cvp[sr].nd = dp[1][sr];
	while(!p.empty()){
		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;
			ll mn0 = min(cvp[node].st, dp[0][coc]);
			ll mn1 = min(cvp[node].nd, dp[1][coc]);
			if(en[node] + uz < en[coc]){
				en[coc] = en[node] + uz;
				cvp[coc] = mp(mn0, mn1);
				if(!us[coc])
					p.push(mp(-en[coc] , coc ));
			}
			if(en[node] + uz == en[coc])
				if(mn0 + mn1 < cvp[coc].st + cvp[coc].nd)
					cvp[coc] = mp(mn0, mn1);
		}
	}
	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 (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: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:59: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:85: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:88: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: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45