Submission #636931

#	Time	Username	Problem	Language	Result	Execution time	Memory
636931		chjiao	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	342 ms	20936 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;
vector<vector<pair<ll,ll>>> neighbors(1e5);
vector<ll> du(1e5+1, MAX/2);
vector<ll> dv(1e5+1, MAX/2);
vector<ll> dp(1e5+1, MAX/2);
vector<ll> dpu(1e5+1, MAX/2);
vector<ll> dpv(1e5+1, MAX/2);
const int mn = 1e5+1;
bool vis[mn];
ll ans;

void dijkstra(int s, vector<ll> &d) { // Source and destination
    fill(vis, vis + mn, false);
	using T = pair<ll,ll>; 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;
        }
        vis[pos] = true;
		for (auto x: neighbors[pos]) {
			// If we can reach a neighbouring node faster,
			// we update its minimum distance
            int place; ll value;
            tie(place, value) = x;

			if (d[pos]+value < d[place]) {
                d[place] = d[pos]+value;
				pq.push({d[place], place});
			}
		}
	}
}
void dijkstra2(int start, int end) { // Source and destination
    fill(vis,vis+mn , false);
    fill(dpu.begin(),dpu.end(),MAX/2);
    fill(dpv.begin(), dpv.end(), MAX/2);

	priority_queue<pair<ll,pair<int, int>>> pq;
	pq.push({0, {start,0}});
  
    dp[start] = 0;

	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;
            dp[curr] =  -cost;
        dpu[curr] = min(dpu[last], du[curr]);
        dpv[curr] = min(dpv[last], dv[curr]);
		for (auto x : neighbors[curr]) {
			// If we can reach a neighbouring node faster,
			// we update its minimum distance
            int place; ll value;
            tie(place,value) = x;
            if(dp[place]> dp[curr]+value){
                pq.push({cost-value,{place, curr}});
            }
		}
        }else if(-cost == dp[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); 
    int 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: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45