Submission #636817

#	Time	Username	Problem	Language	Result	Execution time	Memory
636817		chjiao	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	115 ms	22056 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<int,int>>> neighbors(1e5);
vector<int> du(1e5, INT_MAX/2);
vector<int> dv(1e5, INT_MAX/2);
vector<int> dp(1e5, INT_MAX/2);
vector<int> dpu(1e5, INT_MAX/2);
vector<int> dpv(1e5, INT_MAX/2);
const int mn = 1e5;
bool vis[mn];
int ans;

void dijkstra(int s, vector<int> &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], value});
			}
		}
	}
}
void dijkstra2(int start, int end) { // Source and destination
    fill(vis,vis+mn , false);
    fill(dpu.begin(),dpu.end(),INT_MAX/2);
    fill(dpv.begin(), dpu.end(), INT_MAX/2);

	priority_queue<pair<ll,pair<int, int>>> pq;
	pq.push({0, {start,0}});
    dpu[0]= INT_MAX/2;
    dpv[0] = INT_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;
        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(dp[place]> dp[curr]+value){
                pq.push({-cost-value,{place, curr}});
            }
		}
        }else{
            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
    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;


}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra(int, std::vector<int>&)':
commuter_pass.cpp:29:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |   for (auto [place, value]: neighbors[pos]) {
      |             ^
commuter_pass.cpp: In function 'void dijkstra2(int, int)':
commuter_pass.cpp:60:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |   for (auto [place, value] : neighbors[curr]) {
      |             ^

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