답안 #407044

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
407044	2021-05-18T11:49:35 Z	evilbuggy	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	855 ms	25636 KB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
const int M = 200005;
const long long inf = (long long)1e18;
vector<int> g[N];
int a[M], b[M], c[M], vis[N];
long long dists[N], distt[N];
long long distu[N], distv[N];
long long pref[N], suff[N];

inline void distances(int n, long long dist[], int s){
	for(int i = 1; i <= n; i++){
		dist[i] = inf;
		vis[i] = 0;
	}
	set<pair<long long, int> > st;
	st.insert({0, s});
	dist[s] = 0;
	while(!st.empty()){
		auto pp = *st.begin();
		int u = pp.second;
		st.erase(pp);
		if(vis[u])continue;
		vis[u] = 1;
		for(int i : g[u]){
			int v = a[i]^b[i]^u;
			if(dist[v] > dist[u] + c[i]){
				dist[v] = dist[u] + c[i];
				st.insert({dist[v], v});
			}
		}
	}
}

long long compute(int n, int s, int t, int flg){
	vector<pair<long long, int> > vec;
	for(int i = 1; i <= n; i++){
		pref[i] = dists[i];
		suff[i] = distt[i];
		if(flg){
			pref[i] += distu[i];
			suff[i] += distv[i];
		}else{
			pref[i] += distv[i];
			suff[i] += distu[i];
		}
		vec.push_back({dists[i], i});
	}
	sort(vec.begin(), vec.end());
	for(auto pp : vec){
		int u = pp.second;
		for(int i : g[u]){
			int v = a[i]^b[i]^u;
			if(dists[u] + c[i] + distt[v] == dists[t]){
				pref[v] = min(pref[v], pref[u] + c[i]);
			}
		}
	}
	reverse(vec.begin(), vec.end());
	for(auto pp : vec){
		int u = pp.second;
		for(int i : g[u]){
			int v = a[i]^b[i]^u;
			if(dists[v] + c[i] + distt[u] == dists[t]){
				suff[v] = min(suff[v], suff[u] + c[i]);
			}
		}
	}
	long long ret = inf;
	for(int i = 1; i <= n; i++){
		ret = min(ret, pref[i] + suff[i]);
	}
	return ret;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n, m;
	cin >> n >> m;
	int s, t;
	cin >> s >> t;
	int u, v;
	cin >> u >> v;
	for(int i = 1; i <= m; i++){
		cin >> a[i] >> b[i] >> c[i];
		g[a[i]].push_back(i);
		g[b[i]].push_back(i);
	}
	distances(n, dists, s);
	distances(n, distt, t);
	distances(n, distu, u);
	distances(n, distv, v);
	long long ans = inf;
	ans = min(ans, compute(n, s, t, 0));
	ans = min(ans, compute(n, s, t, 1));
	ans = min(ans - dists[t], distu[v]);
	cout << ans << '\n';

	return 0;
}

Subtask #1
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	742 ms	21884 KB	Output is correct
2	Correct	614 ms	22980 KB	Output is correct
3	Correct	603 ms	23636 KB	Output is correct
4	Correct	732 ms	23968 KB	Output is correct
5	Correct	652 ms	22528 KB	Output is correct
6	Correct	855 ms	24472 KB	Output is correct
7	Correct	643 ms	22928 KB	Output is correct
8	Correct	620 ms	23300 KB	Output is correct
9	Correct	663 ms	24144 KB	Output is correct
10	Correct	503 ms	23856 KB	Output is correct
11	Correct	222 ms	17652 KB	Output is correct
12	Correct	612 ms	23152 KB	Output is correct

Subtask #2
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	696 ms	21580 KB	Output is correct
2	Correct	641 ms	22724 KB	Output is correct
3	Correct	682 ms	23812 KB	Output is correct
4	Correct	707 ms	22676 KB	Output is correct
5	Correct	668 ms	22736 KB	Output is correct
6	Correct	577 ms	23416 KB	Output is correct
7	Correct	653 ms	22596 KB	Output is correct
8	Correct	681 ms	23676 KB	Output is correct
9	Correct	645 ms	23676 KB	Output is correct
10	Correct	657 ms	23892 KB	Output is correct
11	Correct	245 ms	17704 KB	Output is correct
12	Correct	619 ms	24508 KB	Output is correct

Subtask #3
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	3276 KB	Output is correct
2	Correct	3 ms	2764 KB	Output is correct
3	Correct	3 ms	2764 KB	Output is correct
4	Correct	24 ms	3952 KB	Output is correct
5	Correct	13 ms	3344 KB	Output is correct
6	Correct	3 ms	2764 KB	Output is correct
7	Correct	4 ms	2764 KB	Output is correct
8	Correct	5 ms	2764 KB	Output is correct
9	Correct	3 ms	2764 KB	Output is correct
10	Correct	11 ms	3276 KB	Output is correct
11	Correct	3 ms	2636 KB	Output is correct
12	Correct	2 ms	2764 KB	Output is correct
13	Correct	3 ms	2764 KB	Output is correct
14	Correct	3 ms	2764 KB	Output is correct
15	Correct	3 ms	2764 KB	Output is correct

Subtask #4
45.0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	742 ms	21884 KB	Output is correct
2	Correct	614 ms	22980 KB	Output is correct
3	Correct	603 ms	23636 KB	Output is correct
4	Correct	732 ms	23968 KB	Output is correct
5	Correct	652 ms	22528 KB	Output is correct
6	Correct	855 ms	24472 KB	Output is correct
7	Correct	643 ms	22928 KB	Output is correct
8	Correct	620 ms	23300 KB	Output is correct
9	Correct	663 ms	24144 KB	Output is correct
10	Correct	503 ms	23856 KB	Output is correct
11	Correct	222 ms	17652 KB	Output is correct
12	Correct	612 ms	23152 KB	Output is correct
13	Correct	696 ms	21580 KB	Output is correct
14	Correct	641 ms	22724 KB	Output is correct
15	Correct	682 ms	23812 KB	Output is correct
16	Correct	707 ms	22676 KB	Output is correct
17	Correct	668 ms	22736 KB	Output is correct
18	Correct	577 ms	23416 KB	Output is correct
19	Correct	653 ms	22596 KB	Output is correct
20	Correct	681 ms	23676 KB	Output is correct
21	Correct	645 ms	23676 KB	Output is correct
22	Correct	657 ms	23892 KB	Output is correct
23	Correct	245 ms	17704 KB	Output is correct
24	Correct	619 ms	24508 KB	Output is correct
25	Correct	16 ms	3276 KB	Output is correct
26	Correct	3 ms	2764 KB	Output is correct
27	Correct	3 ms	2764 KB	Output is correct
28	Correct	24 ms	3952 KB	Output is correct
29	Correct	13 ms	3344 KB	Output is correct
30	Correct	3 ms	2764 KB	Output is correct
31	Correct	4 ms	2764 KB	Output is correct
32	Correct	5 ms	2764 KB	Output is correct
33	Correct	3 ms	2764 KB	Output is correct
34	Correct	11 ms	3276 KB	Output is correct
35	Correct	3 ms	2636 KB	Output is correct
36	Correct	2 ms	2764 KB	Output is correct
37	Correct	3 ms	2764 KB	Output is correct
38	Correct	3 ms	2764 KB	Output is correct
39	Correct	3 ms	2764 KB	Output is correct
40	Correct	766 ms	24472 KB	Output is correct
41	Correct	712 ms	23496 KB	Output is correct
42	Correct	656 ms	23556 KB	Output is correct
43	Correct	251 ms	17688 KB	Output is correct
44	Correct	256 ms	17788 KB	Output is correct
45	Correct	565 ms	22320 KB	Output is correct
46	Correct	577 ms	22136 KB	Output is correct
47	Correct	788 ms	23876 KB	Output is correct
48	Correct	256 ms	17132 KB	Output is correct
49	Correct	538 ms	25636 KB	Output is correct
50	Correct	535 ms	22728 KB	Output is correct
51	Correct	546 ms	22184 KB	Output is correct

답안 #407044

Compilation message

Subtask #1 16.0 / 16.0

Subtask #2 15.0 / 15.0

Subtask #3 24.0 / 24.0

Subtask #4 45.0 / 45.0

Subtask #1
16.0 / 16.0

Subtask #2
15.0 / 15.0

Subtask #3
24.0 / 24.0

Subtask #4
45.0 / 45.0