Submission #331582

#	Time	Username	Problem	Language	Result	Execution time	Memory
331582		limabeans	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	441 ms	24800 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const ll inf = 1e18;

void spa(const vector<vector<pair<ll,int>>>& g, vector<ll>& dist, int src) {
    int n = g.size();
    dist.clear();
    dist.resize(n);
    for (int i=0; i<n; i++) {
	dist[i] = inf;
    }
    dist[src] = 0;
    priority_queue<pair<ll,int>> pq;
    pq.emplace(0,src);
    while (!pq.empty()) {
	auto cur = pq.top();
	pq.pop();
	ll wei = -cur.first;
	int at = cur.second;
	if (wei > dist[at]) continue;
	for (auto ed: g[at]) {
	    ll d = ed.first;
	    int to = ed.second;
	    if (wei+d < dist[to]) {
		dist[to] = wei+d;
		pq.emplace(-dist[to], to);
	    }
	}
    }
}

int n, m;
vector<vector<pair<ll,int>>> g;

int s,t,u,v;


vector<ll> ds,dt,du,dv;



vector<ll> dpT; //dpT[x] = min dist x->v, while we walk from T-->S




ll solveT(int at) {
    if (ds[at]+dt[at]!=dt[s]) return inf;
    if (dpT[at]!=inf) return dpT[at];
    ll &res = dpT[at] = dv[at];


    for (auto ed: g[at]) {
	int to = ed.second;
	ll wei = ed.first;
	if (ds[at] == wei+ds[to]) {
	    res = min(res, solveT(to));
	}
    }

    return res;
}



vector<ll> dpS;

ll solveS(int at) {
    if (ds[at]+dt[at]!=dt[s]) return inf;
    if (dpS[at]!=inf) return dpS[at];

    ll &res = dpS[at] = dv[at];

    for (auto ed: g[at]) {
	ll wei = ed.first;
	int to = ed.second;
	if (dt[at]==wei+dt[to]) {
	    res = min(res, solveS(to));
	}
    }


    return res;
}


int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>m;
    cin>>s>>t>>u>>v;
    --s;--t;--u;--v;
    g.resize(n);
    for (int i=0; i<m; i++) {
	int u,v,w; cin>>u>>v>>w;
	--u; --v;
	g[u].push_back({w,v});
	g[v].push_back({w,u});
    }


    spa(g,ds,s);
    spa(g,dt,t);
    spa(g,du,u);
    spa(g,dv,v);


    dpT.resize(n, inf);
    solveT(t);
    
    dpS.resize(n, inf);
    solveS(s);


    ll res = du[v];

    for (int i=0; i<n; i++) {
	res = min(res, du[i]+min(dpS[i],dpT[i]));
    }


    cout<<res<<endl;    
    return 0;
}

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45