Submission #41087

#	Time	Username	Problem	Language	Result	Execution time	Memory
41087		kriii	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	439 ms	15640 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 'int main()':
commuter_pass.cpp:30:47: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d %d %d %d %d %d",&N,&M,&S,&T,&U,&V);
                                               ^
commuter_pass.cpp:33:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   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