Submission #636923

#	Time	Username	Problem	Language	Result	Execution time	Memory
636923		chjiao	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	480 ms	27440 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+1;
vector<vector<pair<ll,ll>>> 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);

// ll du[mn],dv[mn], ds[mn], dpu[mn], dpv[mn];


bool vis[mn];
ll ans;
 
void dijkstra(ll s, vector<ll>& d) { // Source and destination
	// fill(vis, vis + 100001, false);  //初始化visited为false

	// priority_queue<pair<ll, ll>> pq;
	// pq.push({0, s});
	// while (!pq.empty()) {
	// 	ll c, node;
	// 	tie(c, node) = pq.top();  //c: 从 start 到 node 的cost
	// 	pq.pop();

	// 	if (!vis[node]) {
	// 		d[node] = -c;   //距离
	// 		vis[node] = true;
	// 		for (auto& i : neighbors[node]) pq.push({c - i.second, i.first});
	// 	}
	// }

    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()) {
        ll pos, cost;
		tie(cost, pos) = pq.top();
        pq.pop();
        if(vis[pos]==true){
            continue;
        }
       
        if(!vis[pos]) {
             vis[pos] = true;
             d[pos] = cost;
             for (auto & [place, value]: neighbors[pos]) {
                pq.push({cost+value, place});
             } 

        }
		// 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);
    // fill(dpu,dpu + mn,LLONG_MAX/2);
    // fill(dpv, dpv+mn, LLONG_MAX/2);

    	priority_queue<pair<ll, pair<ll, ll>>> pq;
	pq.push({0, {start, 0}});   //cost, curr node, pre node
	dpu[0] = dpv[0] = LLONG_MAX/ 2;
	while (!pq.empty()) {
		ll c, node, par;
		pair<ll, ll> p;
		tie(c, p) = pq.top();
		tie(node, par) = p;
		pq.pop();

		if (!vis[node]) {
			vis[node] = true;
			ds[node] = -c;
			dpu[node] = min(du[node], dpu[par]);
			dpv[node] = min(dv[node], dpv[par]);
			for (auto i : neighbors[node]) pq.push({c - i.second, {i.first, node}});  //
		} else if (-c == ds[node]) { //另外一条最短路近
			if (min(du[node], dpu[par]) + min(dv[node], dpv[par]) <= dpu[node] + dpv[node]) {
				dpu[node] = min(du[node], dpu[par]);
				dpv[node] = min(dv[node], dpv[par]);
			}
		}
	}

	ans = min(ans, dpu[end] + dpv[end]);

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