oj.uz

Submission #61852

# Submission time Handle Problem Language Result Execution time Memory
61852 2018-07-26T22:11:26 Z kingpig9 Commuter Pass (JOI18_commuter_pass) C++11
100 / 100
 982 ms 83172 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll, int> edge;
const int MAXN = 100010;
const ll INF = 0x0101010101010101;

//#define debug(...) fprintf(stderr, __VA_ARGS__)
#define debug(...)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

void setmin (ll &a, ll b) {
	if (a > b) {
		a = b;
	}
}

int N, M, S, T, U, V;
vector<edge> adj[MAXN];
ll sdist[MAXN], tdist[MAXN], udist[MAXN], vdist[MAXN];
bool vis[MAXN];

void dijkstra (ll *dist, int s) {
	fill_n(dist + 1, N, INF);
	fill_n(vis + 1, N, false);
	dist[s] = 0;
	priority_queue<edge, vector<edge>, greater<edge>> pq;
	pq.emplace(0ll, s);

	while (!pq.empty()) {
		int u = pq.top().se;
		ll w = pq.top().fi;
		pq.pop();

		if (vis[u]) {
			continue;
		}
		vis[u] = true;

		for (edge e : adj[u]) {
			ll nw = w + e.fi;
			int v = e.se;
			if (nw < dist[v]) {
				dist[v] = nw;
				pq.emplace(nw, v);
			}
		}
	}
}

ll dp[MAXN];
vector<int> dag[MAXN];

ll getdp (int x) {
	ll &ref = dp[x];
	if (ref != INF) {
		return ref;
	}
	ref = vdist[x];

	for (int y : dag[x]) {
		setmin(ref, getdp(y));
	}
	return ref;
}

ll go() {
	debug("---------PROPAGANDA--------\n");
#warning reset EVERYTHING!
	dijkstra(sdist, S);
	dijkstra(tdist, T);
	dijkstra(udist, U);
	dijkstra(vdist, V);

	//now start the work - calc SP dag
	//U -> vertex -> somewhere in sub of vertex -> V
	fillchar(dp, 1);

	for (int i = 1; i <= N; i++) {
		dag[i].clear();
		for (edge e : adj[i]) {
			int j = e.se;
			//S -> i -> j -> T
			if (sdist[i] + e.fi + tdist[j] == sdist[T]) {
				debug("%d -> %d\n", i, j);
				dag[i].push_back(j);
			}
		}
	}

	ll ans = udist[V];
	for (int i = 1; i <= N; i++) {
		setmin(ans, udist[i] + getdp(i));
	}
	return ans;
}

int main() {
	scanf("%d %d %d %d %d %d", &N, &M, &S, &T, &U, &V);
	for (int i = 1; i <= M; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		adj[a].emplace_back(c, b);
		adj[b].emplace_back(c, a);
	}

	ll ans = INF;
	for (int qi = 0; qi < 2; qi++) {
		swap(U, V);
		setmin(ans, go());
	}
	printf("%lld\n", ans);
}

Compilation message

commuter_pass.cpp:73:2: warning: #warning reset EVERYTHING! [-Wcpp]
 #warning reset EVERYTHING!
  ^~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:103: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:106:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &a, &b, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 982 ms 26524 KB Output is correct
2 Correct 851 ms 29252 KB Output is correct
3 Correct 897 ms 36252 KB Output is correct
4 Correct 715 ms 37792 KB Output is correct
5 Correct 781 ms 40924 KB Output is correct
6 Correct 823 ms 45380 KB Output is correct
7 Correct 843 ms 48736 KB Output is correct
8 Correct 874 ms 51976 KB Output is correct
9 Correct 951 ms 55224 KB Output is correct
10 Correct 702 ms 59540 KB Output is correct
11 Correct 410 ms 59540 KB Output is correct
12 Correct 920 ms 65992 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 970 ms 70524 KB Output is correct
2 Correct 829 ms 74084 KB Output is correct
3 Correct 848 ms 77416 KB Output is correct
4 Correct 804 ms 78152 KB Output is correct
5 Correct 967 ms 78272 KB Output is correct
6 Correct 850 ms 82592 KB Output is correct
7 Correct 804 ms 83172 KB Output is correct
8 Correct 980 ms 83172 KB Output is correct
9 Correct 976 ms 83172 KB Output is correct
10 Correct 951 ms 83172 KB Output is correct
11 Correct 320 ms 83172 KB Output is correct
12 Correct 790 ms 83172 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 83172 KB Output is correct
2 Correct 8 ms 83172 KB Output is correct
3 Correct 7 ms 83172 KB Output is correct
4 Correct 33 ms 83172 KB Output is correct
5 Correct 22 ms 83172 KB Output is correct
6 Correct 10 ms 83172 KB Output is correct
7 Correct 10 ms 83172 KB Output is correct
8 Correct 13 ms 83172 KB Output is correct
9 Correct 9 ms 83172 KB Output is correct
10 Correct 22 ms 83172 KB Output is correct
11 Correct 7 ms 83172 KB Output is correct
12 Correct 9 ms 83172 KB Output is correct
13 Correct 8 ms 83172 KB Output is correct
14 Correct 9 ms 83172 KB Output is correct
15 Correct 8 ms 83172 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 982 ms 26524 KB Output is correct
2 Correct 851 ms 29252 KB Output is correct
3 Correct 897 ms 36252 KB Output is correct
4 Correct 715 ms 37792 KB Output is correct
5 Correct 781 ms 40924 KB Output is correct
6 Correct 823 ms 45380 KB Output is correct
7 Correct 843 ms 48736 KB Output is correct
8 Correct 874 ms 51976 KB Output is correct
9 Correct 951 ms 55224 KB Output is correct
10 Correct 702 ms 59540 KB Output is correct
11 Correct 410 ms 59540 KB Output is correct
12 Correct 920 ms 65992 KB Output is correct
13 Correct 970 ms 70524 KB Output is correct
14 Correct 829 ms 74084 KB Output is correct
15 Correct 848 ms 77416 KB Output is correct
16 Correct 804 ms 78152 KB Output is correct
17 Correct 967 ms 78272 KB Output is correct
18 Correct 850 ms 82592 KB Output is correct
19 Correct 804 ms 83172 KB Output is correct
20 Correct 980 ms 83172 KB Output is correct
21 Correct 976 ms 83172 KB Output is correct
22 Correct 951 ms 83172 KB Output is correct
23 Correct 320 ms 83172 KB Output is correct
24 Correct 790 ms 83172 KB Output is correct
25 Correct 19 ms 83172 KB Output is correct
26 Correct 8 ms 83172 KB Output is correct
27 Correct 7 ms 83172 KB Output is correct
28 Correct 33 ms 83172 KB Output is correct
29 Correct 22 ms 83172 KB Output is correct
30 Correct 10 ms 83172 KB Output is correct
31 Correct 10 ms 83172 KB Output is correct
32 Correct 13 ms 83172 KB Output is correct
33 Correct 9 ms 83172 KB Output is correct
34 Correct 22 ms 83172 KB Output is correct
35 Correct 7 ms 83172 KB Output is correct
36 Correct 9 ms 83172 KB Output is correct
37 Correct 8 ms 83172 KB Output is correct
38 Correct 9 ms 83172 KB Output is correct
39 Correct 8 ms 83172 KB Output is correct
40 Correct 793 ms 83172 KB Output is correct
41 Correct 842 ms 83172 KB Output is correct
42 Correct 858 ms 83172 KB Output is correct
43 Correct 428 ms 83172 KB Output is correct
44 Correct 408 ms 83172 KB Output is correct
45 Correct 799 ms 83172 KB Output is correct
46 Correct 812 ms 83172 KB Output is correct
47 Correct 848 ms 83172 KB Output is correct
48 Correct 400 ms 83172 KB Output is correct
49 Correct 683 ms 83172 KB Output is correct
50 Correct 859 ms 83172 KB Output is correct
51 Correct 788 ms 83172 KB Output is correct