Submission #45523

#	Time	Username	Problem	Language	Result	Execution time	Memory
45523		reality	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	702 ms	208416 KiB

commuter_pass

#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
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45