Submission #758605

#	Time	Username	Problem	Language	Result	Execution time	Memory
758605		KN200711	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	377 ms	26576 KiB

commuter_pass

# include <bits/stdc++.h>
# define fi first
# define se second
# define ll long long
using namespace std;

int N, M;
int S, T, U, V;
vector< pair<int, int> > edge[100001];

ll mn[4][100001];
bool vis[100001];

void djks(int id) {
	int st;
	if(id == 0) st = S;
	else if(id == 1) st = T;
	else if(id == 2) st = U;
	else st = V;
	
	for(int i=1;i<=N;i++) vis[i] = 0;
	
	priority_queue< pair<ll, int> > PQ;
	PQ.push(make_pair(0, st));	
	
	while(!PQ.empty()) {
		ll a = -PQ.top().fi;
		int b = PQ.top().se;
		PQ.pop();
		if(vis[b]) continue;
		vis[b] = 1;
		mn[id][b] = a;
		
		for(auto p : edge[b]) {
			if(!vis[p.fi]) PQ.push(make_pair(-a-p.se, p.fi));
		}
	}
	return;
}

vector<int> adj[100001]; // path from S to T in the most efficient ways
ll pth[4][100001];

ll fn(int a, int id) {
//	cout<<a<<endl;
	if(pth[id][a] != 1e18) return pth[id][a];
	pth[id][a] = mn[id][a];
	for(auto p : adj[a]) {
		pth[id][a] = min(pth[id][a], fn(p, id));
	}
	return pth[id][a];
}

int main() {
	scanf("%d %d", &N, &M);
	scanf("%d %d %d %d", &S, &T, &U, &V);
	
	vector< pair< pair<int, int>, int> > jj;
	jj.clear();
	for(int i=0;i<M;i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		jj.push_back(make_pair(make_pair(a, b), c));
		edge[a].push_back(make_pair(b, c));
		edge[b].push_back(make_pair(a, c));
	}
	for(int i=0;i<4;i++) djks(i);
	
	ll cs = mn[0][T];
	for(auto p : jj) {
		if(mn[0][p.fi.fi] + p.se + mn[1][p.fi.se] == cs) {
			adj[p.fi.fi].push_back(p.fi.se);
		} else if(mn[0][p.fi.se] + p.se + mn[1][p.fi.fi] == cs) {
			adj[p.fi.se].push_back(p.fi.fi);
		}
	}
	
	for(int i=1;i<=N;i++) pth[2][i] = pth[3][i] = 1e18;
	ll ans = mn[2][V];
	for(int i=1;i<=N;i++) {
	//	cout<<i<<" "<<mn[2][i]<<" "<<mn[3][i]<<endl;
		ans = min(ans, fn(i, 2) + mn[3][i]);
		ans = min(ans, fn(i, 3) + mn[2][i]);
	}
	printf("%lld\n", ans);
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |  scanf("%d %d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~~
commuter_pass.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |  scanf("%d %d %d %d", &S, &T, &U, &V);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |   scanf("%d %d %d", &a, &b, &c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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