Submission #125617

#	Time	Username	Problem	Language	Result	Execution time	Memory
125617		gs14004	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	433 ms	22012 KiB

commuter_pass

#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
 
using namespace std;
 
#define MAXN 100005
#define MAXM 200005
 
typedef long long lint;
typedef pair<lint, int> pli;
 
const lint LINF = 1ll << 50;
int N, M, S, T, U, V;
int A[MAXM], B[MAXM];
lint C[MAXM];
vector<pli> ed[MAXN];
priority_queue<pli, vector<pli>, greater<pli> > pq;
lint disS[MAXN], disT[MAXN], disU[MAXN], disV[MAXN];
vector<int> sho;
lint dp[MAXN];
lint ans;
 
void dij(int x, lint dis[]) {
	pq.push(make_pair(0ll, x));
	for(int i = 1; i <= N; i++) dis[i] = LINF;
	dis[x] = 0ll;
	while(!pq.empty()) {
		pli t = pq.top();
		pq.pop();
		if(dis[t.second] != t.first) continue;
		for(auto a : ed[t.second]) if(t.first + a.first < dis[a.second]) {
			dis[a.second] = t.first + a.first;
			pq.push(make_pair(dis[a.second], a.second));
		}
	}
}
 
void solve(int U, int V, lint disU[], lint disV[]) {
	for(auto a : sho) {
		dp[a] = disU[a];
		for(auto b : ed[a]) if(disS[b.second] + disT[b.second] == disS[T] && disS[b.second] < disS[a])
			dp[a] = min(dp[a], dp[b.second]);
		ans = min(ans, dp[a] + disV[a]);
	}
}
 
int main() {
 
	scanf("%d%d%d%d%d%d", &N, &M, &S, &T, &U, &V);
	for(int i = 0; i < M; i++) scanf("%d%d%lld", A + i, B + i, C + i);
 
	for(int i = 0; i < M; i++) {
		ed[A[i]].push_back(make_pair(C[i], B[i]));
		ed[B[i]].push_back(make_pair(C[i], A[i]));
	}
 
	dij(S, disS);
	dij(T, disT);
	dij(U, disU);
	dij(V, disV);
 
	for(int i = 1; i <= N; i++) if(disS[i] + disT[i] == disS[T]) sho.push_back(i);
	sort(sho.begin(), sho.end(), [&](const int &a, const int &b) { return disS[a] < disS[b]; } );
 
	ans = disU[V];
	solve(U, V, disU, disV);
	solve(V, U, disV, disU);
 
	printf("%lld", 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]
  scanf("%d%d%d%d%d%d", &N, &M, &S, &T, &U, &V);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:52:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0; i < M; i++) scanf("%d%d%lld", A + i, B + i, C + i);
                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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