Submission #42297

#	Time	Username	Problem	Language	Result	Execution time	Memory
42297		RezwanArefin01	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	653 ms	21916 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, int> ii; 

const int maxn = 1e5 + 10;
vector<int> adj[maxn], cost[maxn];
vector<ll> du, dv, dt, ds, dp1, dp2;

void dijkstra(int s, int n, vector<ll> &d) {
	for(int i = 0; i < n; i++) d[i] = 1e18;
	priority_queue<ii, vector<ii>, greater<ii> > q;
	q.push({d[s] = 0, s});
	while(!q.empty()) {
		ii x = q.top(); q.pop(); 
		int u = x.second; ll c = x.first;
		for(int i = 0; i < adj[u].size(); i++) {
			int v = adj[u][i]; ll w = cost[u][i];
			if(d[v] > c + w) {
				d[v] = c + w;
				q.push({d[v], v});
			}
		}
	}
}

void compute(int s, int n, vector<ll> &dp, vector<ll> &d) {
	dp.resize(n + 1);
	d.resize(n + 1);
	for(int i = 1; i <= n; i++) {
		dp[i] = du[i]; 
		d[i] = 1e18;
	}
	priority_queue<ii, vector<ii>, greater<ii> > q; 
	q.push({d[s] = 0, s});

	while(!q.empty()) {
		ii x = q.top(); q.pop(); 
		int u = x.second; ll c = x.first;
		for(int i = 0; i < adj[u].size(); i++) {
			int v = adj[u][i]; ll w = cost[u][i];
			if(d[v] == c + w) {
			//	cout << u << " -> " << v << " ";
				d[v] = c + w; 
				dp[v] = min(dp[v], dp[u]);
				//q.push({d[v], v});
			//	cout << dp[u] << " " << dp[v] << endl;
			} else if(d[v] > c + w) {
			//	cout << u << " -> " << v << " " ;
				d[v] = c + w;
				dp[v] = min(du[v], dp[u]);
				q.push({d[v], v});
			//	cout << dp[u] << " " << dp[v] << endl;
			}
		}
	}
}

int main(int argc, char const *argv[]) {
#ifdef LOCAL_TESTING
	freopen("in", "r", stdin);
#endif
	int n, m, u, v, s, t; 
	scanf("%d %d", &n, &m); 
	scanf("%d %d", &s, &t);
	scanf("%d %d", &u, &v);
	for(int i = 0; i < m; i++) {
		int u, v, c;
		scanf("%d %d %d", &u, &v, &c);
		adj[u].push_back(v);
		adj[v].push_back(u);
		cost[u].push_back(c);
		cost[v].push_back(c);
	}	

	du.resize(n + 1);
	dv.resize(n + 1);
	ds.resize(n + 1);
	dt.resize(n + 1);
	dijkstra(u, n + 1, du);
	dijkstra(v, n + 1, dv);

	compute(s, n, dp1, ds); 
	compute(t, n, dp2, dt);

	ll Min = 1e18;

	for(int i = 1; i <= n; i++) {
		if(ds[t] == ds[i] + dt[i]) {
			Min = min(Min, dv[i] + min(dp1[i], dp2[i]));
		}
	}
	cout << min(Min, du[v]) << endl;

}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra(int, int, std::vector<long long int>&)':
commuter_pass.cpp:18:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < adj[u].size(); i++) {
                    ^
commuter_pass.cpp: In function 'void compute(int, int, std::vector<long long int>&, std::vector<long long int>&)':
commuter_pass.cpp:41:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < adj[u].size(); i++) {
                    ^
commuter_pass.cpp: In function 'int main(int, const char**)':
commuter_pass.cpp:65:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m); 
                        ^
commuter_pass.cpp:66:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &s, &t);
                        ^
commuter_pass.cpp:67:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &u, &v);
                        ^
commuter_pass.cpp:70:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &u, &v, &c);
                                ^

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