oj.uz

Submission #60424

# Submission time Handle Problem Language Result Execution time Memory
60424 2018-07-24T07:31:58 Z gusfring Commuter Pass (JOI18_commuter_pass) C++14
16 / 100
 816 ms 73284 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 617 ms 23188 KB Output is correct
2 Correct 748 ms 25664 KB Output is correct
3 Correct 625 ms 29364 KB Output is correct
4 Correct 712 ms 34476 KB Output is correct
5 Correct 741 ms 36644 KB Output is correct
6 Correct 655 ms 41944 KB Output is correct
7 Correct 723 ms 44240 KB Output is correct
8 Correct 804 ms 47692 KB Output is correct
9 Correct 586 ms 51884 KB Output is correct
10 Correct 507 ms 56276 KB Output is correct
11 Correct 246 ms 56276 KB Output is correct
12 Correct 671 ms 62640 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 625 ms 66600 KB Output is correct
2 Correct 673 ms 69896 KB Output is correct
3 Incorrect 816 ms 73284 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 73284 KB Output is correct
2 Incorrect 6 ms 73284 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 617 ms 23188 KB Output is correct
2 Correct 748 ms 25664 KB Output is correct
3 Correct 625 ms 29364 KB Output is correct
4 Correct 712 ms 34476 KB Output is correct
5 Correct 741 ms 36644 KB Output is correct
6 Correct 655 ms 41944 KB Output is correct
7 Correct 723 ms 44240 KB Output is correct
8 Correct 804 ms 47692 KB Output is correct
9 Correct 586 ms 51884 KB Output is correct
10 Correct 507 ms 56276 KB Output is correct
11 Correct 246 ms 56276 KB Output is correct
12 Correct 671 ms 62640 KB Output is correct
13 Correct 625 ms 66600 KB Output is correct
14 Correct 673 ms 69896 KB Output is correct
15 Incorrect 816 ms 73284 KB Output isn't correct
16 Halted 0 ms 0 KB -