Submission #930337

#	Time	Username	Problem	Language	Result	Execution time	Memory
930337		lovrot	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	437 ms	18508 KiB

commuter_pass

#include <algorithm> 
#include <set> 
#include <vector> 
#include <cstdio> 

#define X first
#define Y second
#define PB push_back

using namespace std;

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

const int N = 1e5 + 10; 
const ll OO = 1e18;

int n, m, s, t, a, b;
vector<pii> G[N];

ll DP[N], _DP[N], D[N];

auto comp = [](int a, int b) { return D[a] < D[b] || (D[a] == D[b] && a < b); };
set<int, decltype(comp)> S(comp); 

void dijkstra(int s, vector<ll> &V) {
	for(int i = 1; i <= n; ++i) D[i] = OO;
	D[s] = 0;
	S.insert(s);

	for(; !S.empty(); ) {
		int u = *S.begin();
		S.erase(S.begin()); 

		for(pii e : G[u]) 
			if(D[e.X] > D[u] + e.Y) {
				S.erase(e.X);
				D[e.X] = D[u] + e.Y;
				S.insert(e.X);
			}
	}
	
	V.resize(N);
	for(int i = 1; i <= n; ++i) V[i] = D[i];
}

vector<int> V;
vector<ll> DS, DT, DB, DA;

int main() {
	scanf("%d%d%d%d%d%d", &n, &m, &s, &t, &a, &b);
	for(int i = 0; i < m; ++i) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w); 
		G[u].PB({v, w});
		G[v].PB({u, w});
	}

	dijkstra(s, DS); 
	dijkstra(t, DT);
	dijkstra(b, DB);

	for(int i = 1; i <= n; ++i) {
		V.PB(i); 
		_DP[i] = OO;
		DP[i] = OO;
	}

	sort(V.begin(), V.end(), [](int a, int b) { return DS[a] > DS[b]; });
	for(int u : V) {
		DP[u] = min(DP[u], DB[u]);
		for(pii e : G[u]) 
			if(DS[u] + e.Y + DT[e.X] == DS[t])
				DP[u] = min(DP[u], DP[e.X]);
	}

	reverse(V.begin(), V.end());
	for(int u : V) {
		_DP[u] = min(_DP[u], DB[u]);
		for(pii e : G[u]) 
			if(DT[u] + e.Y + DS[e.X] == DT[s])
				_DP[u] = min(_DP[u], _DP[e.X]);
	}

	ll ans = OO;
	dijkstra(a, DA);
	
	for(int u = 1; u <= n; ++u) ans = min(ans, DA[u] + min(_DP[u], DP[u]));
//	for(int u = 1; u <= n; ++u) printf("%d : a %lld b %lld dp %lld\n", u, DA[u], DB[u], DP[u]);

	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |  scanf("%d%d%d%d%d%d", &n, &m, &s, &t, &a, &b);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |   scanf("%d%d%d", &u, &v, &w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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