oj.uz

Submission #45523

# Submission time Handle Problem Language Result Execution time Memory
45523 2018-04-15T00:16:06 Z reality Commuter Pass (JOI18_commuter_pass) C++17
0 / 100
 702 ms 208416 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;
vector < pii > g[N];
ll D1[N];
ll D2[N];
ll D3[N];
ll D4[N];
int S,T,U,V;
vi g1[N];
vi g2[N];
ll D[N];
int was[N];
int main(void) {
    int n,m;
    cin>>n>>m;
    cin>>S>>T;
    cin>>U>>V;
    while (m --) {
    	int a,b,c;
    	cin>>a>>b>>c;
    	g[a].pb(mp(b,c));
    	g[b].pb(mp(a,c));
    }
    priority_queue < pii , vector < pii > , greater < pii > > Q;
    for (int i = 1;i <= n;++i)
    	D1[i] = D2[i] = D3[i] = D4[i] = 1e18;
    D1[S] = 0;
    Q.push(mp(0,S));
    while (!Q.empty()) {
    	ll cost = Q.top().fi;
    	int node = Q.top().se;
    	Q.pop();
    	if (D1[node] != cost) 
    		continue;
    	for (auto it : g[node])
    		if (D1[it.fi] > D1[node] + it.se)
    			D1[it.fi] = D1[node] + it.se,Q.push(mp(D1[it.fi],it.fi));
    }
    D2[T] = 0;
    Q.push(mp(0,T));
	while (!Q.empty()) {
    	ll cost = Q.top().fi;
    	int node = Q.top().se;
    	Q.pop();
    	if (D2[node] != cost) 
    		continue;
    	for (auto it : g[node])
    		if (D2[it.fi] > D2[node] + it.se)
    			D2[it.fi] = D2[node] + it.se,Q.push(mp(D2[it.fi],it.fi));
    }
    D3[U] = 0;
    Q.push(mp(0,U));
    while (!Q.empty()) {
    	ll cost = Q.top().fi;
    	int node = Q.top().se;
    	Q.pop();
    	if (D3[node] != cost)
    		continue;
    	for (auto it : g[node])
    		if (D3[it.fi] > D3[node] + it.se)
    			D3[it.fi] = D3[node] + it.se,Q.push(mp(D3[it.fi],it.fi));
    }
    D4[V] = 0;
    Q.push(mp(0,V));
    while (!Q.empty()) {
    	ll cost = Q.top().fi;
    	int node = Q.top().se;
    	Q.pop();
    	if (D4[node] != cost)
    		continue;
    	for (auto it : g[node])
    		if (D4[it.fi] > D4[node] + it.se)
    			D4[it.fi] = D4[node] + it.se,Q.push(mp(D4[it.fi],it.fi));
    }
    const ll dst = D1[T];
    for (int i = 1;i <= n;++i) {
    	for (auto it : g[i]) {
    		if (D1[i] + it.se + D2[it.fi] == dst)
    			g1[i].pb(it.fi),g2[it.fi].pb(i);
		}
    }
    queue < int > q;
    q.push(S);
    was[S] = 1;
    vi order;
    while (!q.empty()) {
    	int node = q.front();
    	order.pb(node);
    	q.pop();
    	for (auto it : g1[node])
    		assert(!was[it]),q.push(it),was[it] = 1;
    }
    ll ans = 1e18;
    for (int i = 1;i <= n;++i)
    	D[i] = D3[i];
    for (auto u : order)
    	for (auto v : g2[u])
    		smin(D[u],D[v]);
    for (int i = 1;i <= n;++i)
    	smin(ans,D[i] + D4[i]);
    for (int i = 1;i <= n;++i)
    	D[i] = D3[i];
    reverse(all(order));
    for (auto u : order)
    	for (auto v : g1[u])
    		smin(D[u],D[v]);
    for (int i = 1;i <= n;++i)
    	smin(ans,D[i] + D4[i]);
    reverse(all(order));
    for (int i = 1;i <= n;++i)
    	D[i] = D4[i];
    for (auto u : order)
    	for (auto v : g2[u])
    		smin(D[u],D[v]);
    for (int i = 1;i <= n;++i)
    	smin(ans,D[i] + D3[i]);
    for (int i = 1;i <= n;++i)
    	D[i] = D4[i];
    reverse(all(order));
    for (auto u : order)
    	for (auto v : g1[u])
    		smin(D[u],D[v]);
    for (int i = 1;i <= n;++i)
    	smin(ans,D[i] + D3[i]);
    cout << ans << '\n';
    return 0;
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 627 ms 85608 KB Output is correct
2 Runtime error 702 ms 172288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 670 ms 176772 KB Output is correct
2 Correct 663 ms 180576 KB Output is correct
3 Correct 636 ms 183644 KB Output is correct
4 Correct 662 ms 187504 KB Output is correct
5 Correct 662 ms 191484 KB Output is correct
6 Correct 661 ms 196892 KB Output is correct
7 Correct 687 ms 200708 KB Output is correct
8 Correct 655 ms 201940 KB Output is correct
9 Correct 669 ms 205720 KB Output is correct
10 Correct 667 ms 208416 KB Output is correct
11 Incorrect 239 ms 208416 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 160 ms 208416 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 627 ms 85608 KB Output is correct
2 Runtime error 702 ms 172288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -