Submission #706093

#	Time	Username	Problem	Language	Result	Execution time	Memory
706093		MarwenElarbi	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	290 ms	19424 KiB

commuter_pass

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
 
vector<pair<int, int> > G[100100];
int N,M,S,T,U,V;
 
vector<long long> dist(int s)
{
	vector<long long> ret(N,1e18);
	priority_queue<pair<long long, int> > Q;
	Q.push({0,s}); ret[s] = 0;
	while (!Q.empty()){
		long long c = -Q.top().first; int x = Q.top().second; Q.pop();
		if (ret[x] < c) continue;
		for (auto &e : G[x]){
			int y = e.first; long long nc = c + e.second;
			if (ret[y] > nc){
				Q.push({-nc,y}); ret[y] = nc;
			}
		}
	}
	return move(ret);
}
 
int main()
{
	scanf ("%d %d %d %d %d %d",&N,&M,&S,&T,&U,&V);
	S--; T--; U--; V--;
	for (int i=0;i<M;i++){
		int x,y,c; scanf ("%d %d %d",&x,&y,&c); x--; y--;
		G[x].push_back({y,c});
		G[y].push_back({x,c});
	}
 
	auto s = dist(S);
	auto t = dist(T);
	auto u = dist(U);
	auto v = dist(V);
 
	vector<pair<long long, int> > st;
	for (int i=0;i<N;i++) if (s[T] == s[i] + t[i]){
		st.push_back({t[i],i});
	}
	sort(st.begin(),st.end());
 
	vector<long long> um(N,1e18), vm(N,1e18);
	long long ans = u[V];
	for (auto &p : st){
		int x = p.second;
		um[x] = u[x];
		vm[x] = v[x];
		for (auto &e : G[x]){
			if (t[e.first] + e.second == t[x]){
				um[x] = min(um[x], um[e.first]);
				vm[x] = min(vm[x], vm[e.first]);
			}
		}
		ans = min(ans,um[x]+v[x]);
		ans = min(ans,vm[x]+u[x]);
	}
 
	printf ("%lld\n",ans);
 
	return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'std::vector<long long int> dist(int)':
commuter_pass.cpp:25:13: warning: moving a local object in a return statement prevents copy elision [-Wpessimizing-move]
   25 |  return move(ret);
      |         ~~~~^~~~~
commuter_pass.cpp:25:13: note: remove 'std::move' call
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |  scanf ("%d %d %d %d %d %d",&N,&M,&S,&T,&U,&V);
      |  ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:33:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |   int x,y,c; scanf ("%d %d %d",&x,&y,&c); x--; y--;
      |              ~~~~~~^~~~~~~~~~~~~~~~~~~~~

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