oj.uz

Submission #58824

# Submission time Handle Problem Language Result Execution time Memory
58824 2018-07-19T15:18:38 Z zadrga Commuter Pass (JOI18_commuter_pass) C++14
0 / 100
 601 ms 23604 KB 
// 16.46
#include <bits/stdc++.h>
 
using namespace std;
 
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF (1LL << 55)
#define MOD (1000 * 1000 * 1000 + 7)
#define maxn 100111

typedef long long ll;
typedef long double ld;
typedef pair<int, ll> pii;

ll len[maxn], d1[maxn], d2[maxn], min1[maxn], min2[maxn];
bool mark[maxn];
vector<pii> adj[maxn], here;

void find_path(int zac, ll d[]){	
	priority_queue<pii> pq;

	d[zac] = 0;
	pq.push(mp(0, zac));

	while(!pq.empty()){
		int x = pq.top().se;
		ll val = -pq.top().fi;
		pq.pop();

		if(val != d[x])
			continue;

		for(pii v : adj[x]){
			if(d[v.fi] > d[x] + v.se){
				d[v.fi] = d[x] + v.se;
				pq.push(mp(-d[v.fi], v.fi));
			}
		}
	}
}

void on_shortest_path(int s, int t, ll d[]){
	queue<int> q;
	q.push(t);
	mark[t] = 1;

	while(!q.empty()){
		int x = q.front();
		q.pop();
		here.pb(mp(d[x], x));

		for(pii v : adj[x]){
			if(!mark[v.fi] && d[x] == d[v.fi] + v.se){
				mark[v.fi] = 1;
				q.push(v.fi);
			}
		}
	}
}

int main(){
	for(int i = 0; i < maxn; i++)
		d1[i] = d2[i] = len[i] = INF;

	int n, m, s, t, u, v;
	scanf("%d%d%d%d%d%d", &n, &m, &s, &t, &u, &v);
	for(int i = 0; i < m; i++){
		int a, b; ll c;
		scanf("%d%d%lld", &a, &b, &c);
		adj[a].pb(mp(b, c));
		adj[b].pb(mp(a, c));
	}

	find_path(s, len);
	find_path(u, d1);
	find_path(v, d2);

	on_shortest_path(s, t, len);


	sort(here.begin(), here.end());
	memset(mark, 0, sizeof(mark));

	ll ans = d1[v];
	for(int i = 0; i < here.size(); i++){
		int x = here[i].se;
		mark[x] = 1;
		min1[x] = d1[x];
		min2[x] = d2[x];

		for(pii cur : adj[x]){
			if(mark[cur.fi]){
				min1[x] = min(min1[x], min1[cur.fi]);
				min2[x] = min(min2[x], min2[cur.fi]);
			}
		}

		ans = min(ans, d1[x] + min2[x]);
		ans = min(ans, d2[x] + min1[x]);
	}

	printf("%lld\n", ans);
	return 0;
}

Compilation message

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:88:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < here.size(); i++){
                 ~~^~~~~~~~~~~~~
commuter_pass.cpp:69: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:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%lld", &a, &b, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 22456 KB Output is correct
2 Correct 512 ms 22456 KB Output is correct
3 Correct 519 ms 23120 KB Output is correct
4 Correct 449 ms 23120 KB Output is correct
5 Correct 486 ms 23292 KB Output is correct
6 Correct 489 ms 23292 KB Output is correct
7 Correct 601 ms 23404 KB Output is correct
8 Correct 547 ms 23404 KB Output is correct
9 Incorrect 259 ms 23404 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 491 ms 23404 KB Output is correct
2 Correct 532 ms 23404 KB Output is correct
3 Correct 409 ms 23404 KB Output is correct
4 Correct 545 ms 23404 KB Output is correct
5 Correct 553 ms 23404 KB Output is correct
6 Correct 493 ms 23604 KB Output is correct
7 Correct 526 ms 23604 KB Output is correct
8 Correct 486 ms 23604 KB Output is correct
9 Correct 500 ms 23604 KB Output is correct
10 Correct 459 ms 23604 KB Output is correct
11 Incorrect 104 ms 23604 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23604 KB Output is correct
2 Correct 7 ms 23604 KB Output is correct
3 Correct 7 ms 23604 KB Output is correct
4 Correct 28 ms 23604 KB Output is correct
5 Correct 20 ms 23604 KB Output is correct
6 Correct 7 ms 23604 KB Output is correct
7 Correct 8 ms 23604 KB Output is correct
8 Correct 11 ms 23604 KB Output is correct
9 Correct 8 ms 23604 KB Output is correct
10 Correct 18 ms 23604 KB Output is correct
11 Incorrect 7 ms 23604 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 22456 KB Output is correct
2 Correct 512 ms 22456 KB Output is correct
3 Correct 519 ms 23120 KB Output is correct
4 Correct 449 ms 23120 KB Output is correct
5 Correct 486 ms 23292 KB Output is correct
6 Correct 489 ms 23292 KB Output is correct
7 Correct 601 ms 23404 KB Output is correct
8 Correct 547 ms 23404 KB Output is correct
9 Incorrect 259 ms 23404 KB Output isn't correct
10 Halted 0 ms 0 KB -