oj.uz

Submission #45655

# Submission time Handle Problem Language Result Execution time Memory
45655 2018-04-15T17:46:50 Z reality Commuter Pass (JOI18_commuter_pass) C++17
100 / 100
 839 ms 52180 KB 
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int N = (int)(1e6) + 5;
ll D1[N];
ll D2[N];
ll D3[N];
ll D4[N];
vector < pii > g[N];
int n;
void Go(ll D[],int S) {
	for (int i = 1;i <= n;++i)
		D[i] = 1e18;
	D[S] = 0;
	priority_queue < pair < ll , int > , vector < pair < ll , int > > , greater < pair < ll , int > > > Q;
	Q.push(mp(0,S));
	while (!Q.empty()) {
		const ll cost = Q.top().fi;
		const int node = Q.top().se;
		Q.pop();
		if (cost != D[node])
			continue;
		for (auto it : g[node])
			if (D[it.fi] > D[node] + it.se)
				D[it.fi] = D[node] + it.se,Q.push(mp(D[it.fi],it.fi));
	}
}
int was[N];
ll d1[N];
ll d2[N];
int main(void)
{
    int m;
    int S,T,U,V;
    cin>>n>>m>>S>>T>>U>>V;
    while (m --) {
    	int a,b,c;
    	cin>>a>>b>>c;
    	g[a].pb(mp(b,c));
    	g[b].pb(mp(a,c));
    }
    Go(D1,S);
    Go(D2,T);
    Go(D3,U);
    Go(D4,V);
    vi points;
    const ll dist = D1[T];
    for (int i = 1;i <= n;++i)
    	if (D1[i] + D2[i] == dist)
    		points.pb(i);
    ll ans = D3[V];
    sort(all(points),[&](int x,int y) {
    		return D1[x] < D1[y];
    	});
    for (auto it : points) {
    	d1[it] = D3[it];
    	d2[it] = D4[it];
    	for (auto edge : g[it]) {
    		if (D1[edge.fi] + edge.se + D2[it] == dist)
    			smin(d1[it],d1[edge.fi]),smin(d2[it],d2[edge.fi]);
    	}
    	smin(ans,d1[it] + D4[it]);
    	smin(ans,d2[it] + D3[it]);
    }
    cout << ans << '\n';
    return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 566 ms 36408 KB Output is correct
2 Correct 573 ms 36408 KB Output is correct
3 Correct 572 ms 36636 KB Output is correct
4 Correct 549 ms 36636 KB Output is correct
5 Correct 547 ms 36636 KB Output is correct
6 Correct 629 ms 36952 KB Output is correct
7 Correct 585 ms 36952 KB Output is correct
8 Correct 544 ms 36952 KB Output is correct
9 Correct 629 ms 36952 KB Output is correct
10 Correct 517 ms 36952 KB Output is correct
11 Correct 233 ms 36952 KB Output is correct
12 Correct 575 ms 36952 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 581 ms 36952 KB Output is correct
2 Correct 621 ms 36952 KB Output is correct
3 Correct 692 ms 36952 KB Output is correct
4 Correct 599 ms 36952 KB Output is correct
5 Correct 765 ms 36952 KB Output is correct
6 Correct 702 ms 36952 KB Output is correct
7 Correct 839 ms 36952 KB Output is correct
8 Correct 643 ms 36952 KB Output is correct
9 Correct 600 ms 36952 KB Output is correct
10 Correct 612 ms 36952 KB Output is correct
11 Correct 273 ms 36952 KB Output is correct
12 Correct 569 ms 36952 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 36952 KB Output is correct
2 Correct 27 ms 36952 KB Output is correct
3 Correct 21 ms 36952 KB Output is correct
4 Correct 72 ms 36952 KB Output is correct
5 Correct 44 ms 36952 KB Output is correct
6 Correct 23 ms 36952 KB Output is correct
7 Correct 24 ms 36952 KB Output is correct
8 Correct 26 ms 36952 KB Output is correct
9 Correct 24 ms 36952 KB Output is correct
10 Correct 45 ms 36952 KB Output is correct
11 Correct 22 ms 36952 KB Output is correct
12 Correct 22 ms 36952 KB Output is correct
13 Correct 23 ms 36952 KB Output is correct
14 Correct 22 ms 36952 KB Output is correct
15 Correct 22 ms 36952 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 566 ms 36408 KB Output is correct
2 Correct 573 ms 36408 KB Output is correct
3 Correct 572 ms 36636 KB Output is correct
4 Correct 549 ms 36636 KB Output is correct
5 Correct 547 ms 36636 KB Output is correct
6 Correct 629 ms 36952 KB Output is correct
7 Correct 585 ms 36952 KB Output is correct
8 Correct 544 ms 36952 KB Output is correct
9 Correct 629 ms 36952 KB Output is correct
10 Correct 517 ms 36952 KB Output is correct
11 Correct 233 ms 36952 KB Output is correct
12 Correct 575 ms 36952 KB Output is correct
13 Correct 581 ms 36952 KB Output is correct
14 Correct 621 ms 36952 KB Output is correct
15 Correct 692 ms 36952 KB Output is correct
16 Correct 599 ms 36952 KB Output is correct
17 Correct 765 ms 36952 KB Output is correct
18 Correct 702 ms 36952 KB Output is correct
19 Correct 839 ms 36952 KB Output is correct
20 Correct 643 ms 36952 KB Output is correct
21 Correct 600 ms 36952 KB Output is correct
22 Correct 612 ms 36952 KB Output is correct
23 Correct 273 ms 36952 KB Output is correct
24 Correct 569 ms 36952 KB Output is correct
25 Correct 51 ms 36952 KB Output is correct
26 Correct 27 ms 36952 KB Output is correct
27 Correct 21 ms 36952 KB Output is correct
28 Correct 72 ms 36952 KB Output is correct
29 Correct 44 ms 36952 KB Output is correct
30 Correct 23 ms 36952 KB Output is correct
31 Correct 24 ms 36952 KB Output is correct
32 Correct 26 ms 36952 KB Output is correct
33 Correct 24 ms 36952 KB Output is correct
34 Correct 45 ms 36952 KB Output is correct
35 Correct 22 ms 36952 KB Output is correct
36 Correct 22 ms 36952 KB Output is correct
37 Correct 23 ms 36952 KB Output is correct
38 Correct 22 ms 36952 KB Output is correct
39 Correct 22 ms 36952 KB Output is correct
40 Correct 575 ms 36952 KB Output is correct
41 Correct 568 ms 36952 KB Output is correct
42 Correct 574 ms 36952 KB Output is correct
43 Correct 305 ms 36952 KB Output is correct
44 Correct 264 ms 36952 KB Output is correct
45 Correct 547 ms 36952 KB Output is correct
46 Correct 541 ms 36952 KB Output is correct
47 Correct 571 ms 40460 KB Output is correct
48 Correct 295 ms 40460 KB Output is correct
49 Correct 539 ms 45924 KB Output is correct
50 Correct 552 ms 48780 KB Output is correct
51 Correct 527 ms 52180 KB Output is correct