Submission #636930

#	Time	Username	Problem	Language	Result	Execution time	Memory
636930		chjiao	Commuter Pass (JOI18_commuter_pass)	C++17	40 / 100	264 ms	18636 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define ll  long long
#define newl '\n'
const int mod = 1e9+7;
const ll MAX = 0x3f3f3f3f3f3f3f3f;
const int mn = 1e5;
vector<vector<pair<int,int>>> neighbors(mn);
vector<ll> du(mn, LLONG_MAX/2);
vector<ll> dv(mn, LLONG_MAX/2);
vector<ll> ds(mn, LLONG_MAX/2);
vector<ll> dpu(mn, LLONG_MAX/2);
vector<ll> dpv(mn, LLONG_MAX/2);
 
bool vis[mn];
ll ans;
 
void dijkstra(ll s, vector<ll> &d) { // Source and destination
    fill(vis, vis + mn, false);
	using T = pair<ll,int>; priority_queue<T,vector<T>,greater<T>> pq;
	d[s] = 0; // The shortest path from a node to itself is 0
	pq.push({0, s});
 
	while (!pq.empty()) {
		int pos = pq.top().second;
        pq.pop();
        if(vis[pos]==true){
            continue;
        }
		for (auto & [place, value]: neighbors[pos]) {
			// If we can reach a neighbouring node faster,
			// we update its minimum distance
			if (d[pos]+value < d[place]) {
                d[place] = d[pos]+value;
				pq.push({d[place], place});
			}
		}
	}
}
void dijkstra2(ll start, ll end) { // Source and destination
    fill(vis,vis+mn , false);
    fill(dpu.begin(),dpu.end(),LLONG_MAX/2);
    fill(dpv.begin(), dpv.end(), LLONG_MAX/2);
 
	priority_queue<pair<ll,pair<ll, ll>>> pq;
	pq.push({0, {start,0}});
    dpu[0]= LLONG_MAX/2;
    dpv[0] = LLONG_MAX/2;
 
	while (pq.size()) {
        ll cost, curr, last;
		cost = pq.top().first;
        curr = pq.top().second.first;
        last = pq.top().second.second;
        pq.pop();
		if(vis[curr]!=true){
            vis[curr] = true;
			ds[curr] = -cost;
			dpu[curr] = min(dpu[last], du[curr]);
			dpv[curr] = min(dpv[last], dv[curr]);
			for (auto [place, value] : neighbors[curr]) {
				// If we can reach a neighbouring node faster,
				// we update its minimum distance
				if(ds[place]> ds[curr]+value){
					pq.push({cost-value,{place, curr}});
				}
			}
        }else if (-cost == ds[curr] ) { 
            if(min(dpu[last], du[curr]) + min(dpv[last], dv[curr]) < dpu[curr]+dpv[curr]){
                dpu[curr] = min(dpu[last], du[curr]);
            	dpv[curr] = min(dpv[last], dv[curr]);
            }
 
        }
	}
    ans = min(ans, dpu[end]+dpv[end]);
}
 
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    // freopen("CommuterPass.in", "r", stdin);
    //freopen("nocross.out", "w", stdout); 
    ll N,M,S,T,U,V,a,b,c;
    cin >> N >> M;
    cin >> S >> T >> U >> V;//s,t is free, U,V needs minimizing
	// S--;T--;U--;V--;
    for(int i=0; i<M; i++){
        cin >> a >> b >> c;
        // a--;
        // b--;
        neighbors[a].push_back(make_pair(b,c));
        neighbors[b].push_back(make_pair(a,c));
 
    }
 
    dijkstra(U, du);
    dijkstra(V, dv);
    ans = du[V];
    dijkstra2(S,T);
    dijkstra2(T,S);
    cout << ans << endl;
}

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