oj.uz

Submission #60563

# Submission time Handle Problem Language Result Execution time Memory
60563 2018-07-24T10:56:11 Z gusfring Commuter Pass (JOI18_commuter_pass) C++14
31 / 100
 787 ms 48748 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 5;
typedef long long ll;

struct node{
	int u;
	ll w;
	bool operator<(const node &rhs) const{
		return w > rhs.w;
	}
};

vector<node> adj[MAXN];
int N, M, S, U, T, V;
ll dists[MAXN], distt[MAXN], distu[MAXN], distv[MAXN];

void dijkstra(int cur, ll *dist){
	for(int i=1; i<=N; ++i) dist[i] = -1;
	dist[cur] = 0;
	priority_queue<node> Q;
	Q.push((node){cur, 0});
	while(!Q.empty()){
		node it = Q.top(); Q.pop();
		int u = it.u;
		ll w = it.w;
		for(node it2 : adj[u]){
			int v = it2.u;
			ll ww = it2.w;
			if(dist[v] == -1 || dist[u] + ww < dist[v]){
				dist[v] = dist[u] + ww;
				Q.push((node){v, dist[v]});
			}
		}
	}
}

int main(){
	scanf("%d %d %d %d %d %d", &N, &M, &S, &T, &U, &V);
	while(M--){
		int u, v, c;
		scanf("%d %d %d", &u, &v, &c);
		adj[u].push_back((node){v, c});
		adj[v].push_back((node){u, c});
	}
	dijkstra(S, dists);
	dijkstra(T, distt);
	dijkstra(U, distu);
	dijkstra(V, distv);
	ll mnu = 1000000000000000000LL, mnv = 1000000000000000000LL, ds = dists[T];
	for(int i=1; i<=N; ++i){
		if(min({dists[i], distt[i], distu[i], distv[i]}) == -1) continue;
		if(dists[i] + distt[i] == ds)	mnu = min(mnu, distu[i]), mnv = min(mnv, distv[i]);
	}
	printf("%lld\n", min(mnu + mnv, distu[V]));
	return 0;
}

Compilation message

commuter_pass.cpp: In function 'void dijkstra(int, ll*)':
commuter_pass.cpp:28:6: warning: unused variable 'w' [-Wunused-variable]
   ll w = it.w;
      ^
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:41: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:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &u, &v, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 678 ms 19376 KB Output is correct
2 Correct 677 ms 19376 KB Output is correct
3 Correct 736 ms 19376 KB Output is correct
4 Correct 632 ms 19596 KB Output is correct
5 Correct 588 ms 19596 KB Output is correct
6 Correct 729 ms 19688 KB Output is correct
7 Correct 723 ms 19688 KB Output is correct
8 Correct 651 ms 19688 KB Output is correct
9 Correct 578 ms 19688 KB Output is correct
10 Correct 509 ms 19688 KB Output is correct
11 Correct 297 ms 19688 KB Output is correct
12 Correct 658 ms 19688 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 669 ms 19688 KB Output is correct
2 Correct 787 ms 19688 KB Output is correct
3 Correct 686 ms 19688 KB Output is correct
4 Correct 760 ms 22032 KB Output is correct
5 Correct 786 ms 25572 KB Output is correct
6 Correct 721 ms 29024 KB Output is correct
7 Correct 741 ms 32588 KB Output is correct
8 Correct 720 ms 36152 KB Output is correct
9 Correct 658 ms 39524 KB Output is correct
10 Correct 688 ms 43172 KB Output is correct
11 Correct 279 ms 43172 KB Output is correct
12 Correct 751 ms 48748 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 48748 KB Output is correct
2 Correct 7 ms 48748 KB Output is correct
3 Incorrect 8 ms 48748 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 678 ms 19376 KB Output is correct
2 Correct 677 ms 19376 KB Output is correct
3 Correct 736 ms 19376 KB Output is correct
4 Correct 632 ms 19596 KB Output is correct
5 Correct 588 ms 19596 KB Output is correct
6 Correct 729 ms 19688 KB Output is correct
7 Correct 723 ms 19688 KB Output is correct
8 Correct 651 ms 19688 KB Output is correct
9 Correct 578 ms 19688 KB Output is correct
10 Correct 509 ms 19688 KB Output is correct
11 Correct 297 ms 19688 KB Output is correct
12 Correct 658 ms 19688 KB Output is correct
13 Correct 669 ms 19688 KB Output is correct
14 Correct 787 ms 19688 KB Output is correct
15 Correct 686 ms 19688 KB Output is correct
16 Correct 760 ms 22032 KB Output is correct
17 Correct 786 ms 25572 KB Output is correct
18 Correct 721 ms 29024 KB Output is correct
19 Correct 741 ms 32588 KB Output is correct
20 Correct 720 ms 36152 KB Output is correct
21 Correct 658 ms 39524 KB Output is correct
22 Correct 688 ms 43172 KB Output is correct
23 Correct 279 ms 43172 KB Output is correct
24 Correct 751 ms 48748 KB Output is correct
25 Correct 21 ms 48748 KB Output is correct
26 Correct 7 ms 48748 KB Output is correct
27 Incorrect 8 ms 48748 KB Output isn't correct
28 Halted 0 ms 0 KB -