oj.uz

Submission #60560

# Submission time Handle Problem Language Result Execution time Memory
60560 2018-07-24T10:51:26 Z gusfring Commuter Pass (JOI18_commuter_pass) C++14
16 / 100
 791 ms 33460 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", mnu + mnv);
	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 659 ms 23296 KB Output is correct
2 Correct 645 ms 25712 KB Output is correct
3 Correct 662 ms 29292 KB Output is correct
4 Correct 544 ms 33416 KB Output is correct
5 Correct 614 ms 33416 KB Output is correct
6 Correct 587 ms 33460 KB Output is correct
7 Correct 645 ms 33460 KB Output is correct
8 Correct 680 ms 33460 KB Output is correct
9 Correct 559 ms 33460 KB Output is correct
10 Correct 455 ms 33460 KB Output is correct
11 Correct 294 ms 33460 KB Output is correct
12 Correct 791 ms 33460 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 703 ms 33460 KB Output is correct
2 Correct 632 ms 33460 KB Output is correct
3 Incorrect 630 ms 33460 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

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

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 659 ms 23296 KB Output is correct
2 Correct 645 ms 25712 KB Output is correct
3 Correct 662 ms 29292 KB Output is correct
4 Correct 544 ms 33416 KB Output is correct
5 Correct 614 ms 33416 KB Output is correct
6 Correct 587 ms 33460 KB Output is correct
7 Correct 645 ms 33460 KB Output is correct
8 Correct 680 ms 33460 KB Output is correct
9 Correct 559 ms 33460 KB Output is correct
10 Correct 455 ms 33460 KB Output is correct
11 Correct 294 ms 33460 KB Output is correct
12 Correct 791 ms 33460 KB Output is correct
13 Correct 703 ms 33460 KB Output is correct
14 Correct 632 ms 33460 KB Output is correct
15 Incorrect 630 ms 33460 KB Output isn't correct
16 Halted 0 ms 0 KB -