Submission #343938

#	Time	Username	Problem	Language	Result	Execution time	Memory
343938		minoum	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	419 ms	23904 KiB

commuter_pass

#include<bits/stdc++.h>

using namespace std;
typedef long long int ll;

const ll inf = LLONG_MAX / 2;
const int MAXN = 1e5 + 10;
int n, m, s, t, x, y;
ll d[4][MAXN], dx[MAXN], dy[MAXN]; // d0:s d1:t d2:x d3:y
vector <pair<int, ll>> adj[MAXN];
priority_queue <pair<ll, int>> q;

inline void dij(int r, int ii){
	for(int i = 0; i < n; i++) d[ii][i] = inf;
	d[ii][r] = 0ll; q.push({0ll, r});
	while(!q.empty()){
		int v = q.top().second; 
		if(-q.top().first > d[ii][v]){
			q.pop();
			continue;
		}
		q.pop();
		for(auto i: adj[v]){
			int u = i.first; ll w = i.second;
			if(w + d[ii][v] < d[ii][u]){
				d[ii][u] = w + d[ii][v];
				q.push({-d[ii][u], u});
			}
		}
	}
	return;
}

inline void dijj(int r){
//	priority_queue <pair<ll, int>> q;
	for(int i = 0; i < n; i++) d[1][i] = inf;
	d[1][r] = 0ll; q.push({0ll, r});
	while(!q.empty()){
		int v = q.top().second; 
		if(-q.top().first > d[1][v]){
			q.pop();
			continue;
		}
		q.pop();
		for(auto i: adj[v]){
			int u = i.first; ll w = i.second;
			if(w + d[1][v] < d[1][u]){
				d[1][u] = w + d[1][v];
				q.push({-d[1][u], u});
			}
			if(w + d[1][v] == d[1][u] && d[1][u]+d[0][u] == d[0][t]){
				dx[u] = min(dx[u], dx[v]);
				dy[u] = min(dy[u], dy[v]);
			}
		}
	}
	return;
}

int main()
{
//	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//	cin >> n >> m >> s >> t >> x >> y; 
	scanf("%d", &n); scanf("%d", &m); scanf("%d", &s); scanf("%d", &t); scanf("%d", &x); scanf("%d", &y);
	s--; t--; x--; y--;
	for(int i = 0; i < m; i++){
		int u,v; ll w;
		//cin >> u >> v >> w; 
		scanf("%d", &u); scanf("%d", &v); scanf("%lld", &w);
		v--; u--;
		adj[v].push_back({u,w});
		adj[u].push_back({v,w});
	}
	dij(x, 2); dij(y, 3);
	for(int i = 0; i < n; i++) dx[i] = d[2][i], dy[i] = d[3][i];
	dij(s, 0); dijj(t); 
	ll ans = d[2][y];
	for(int i = 0; i < n; i++)
		if(d[0][t] == d[0][i] + d[1][i]){
			ans = min(ans, dx[i] + d[3][i]);
			ans = min(ans, dy[i] + d[2][i]);
		}
//	cout << ans;
	printf("%lld", ans)	;
	return 0; 
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |  scanf("%d", &n); scanf("%d", &m); scanf("%d", &s); scanf("%d", &t); scanf("%d", &x); scanf("%d", &y);
      |  ~~~~~^~~~~~~~~~
commuter_pass.cpp:64:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |  scanf("%d", &n); scanf("%d", &m); scanf("%d", &s); scanf("%d", &t); scanf("%d", &x); scanf("%d", &y);
      |                   ~~~~~^~~~~~~~~~
commuter_pass.cpp:64:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |  scanf("%d", &n); scanf("%d", &m); scanf("%d", &s); scanf("%d", &t); scanf("%d", &x); scanf("%d", &y);
      |                                    ~~~~~^~~~~~~~~~
commuter_pass.cpp:64:58: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |  scanf("%d", &n); scanf("%d", &m); scanf("%d", &s); scanf("%d", &t); scanf("%d", &x); scanf("%d", &y);
      |                                                     ~~~~~^~~~~~~~~~
commuter_pass.cpp:64:75: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |  scanf("%d", &n); scanf("%d", &m); scanf("%d", &s); scanf("%d", &t); scanf("%d", &x); scanf("%d", &y);
      |                                                                      ~~~~~^~~~~~~~~~
commuter_pass.cpp:64:92: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |  scanf("%d", &n); scanf("%d", &m); scanf("%d", &s); scanf("%d", &t); scanf("%d", &x); scanf("%d", &y);
      |                                                                                       ~~~~~^~~~~~~~~~
commuter_pass.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |   scanf("%d", &u); scanf("%d", &v); scanf("%lld", &w);
      |   ~~~~~^~~~~~~~~~
commuter_pass.cpp:69:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |   scanf("%d", &u); scanf("%d", &v); scanf("%lld", &w);
      |                    ~~~~~^~~~~~~~~~
commuter_pass.cpp:69:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |   scanf("%d", &u); scanf("%d", &v); scanf("%lld", &w);
      |                                     ~~~~~^~~~~~~~~~~~

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