제출 #636927

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
636927		chjiao	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	348 ms	23840 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);

    	// 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;
    //     c=pq.top().first;
    //     node= pq.top().second.first;
    //     par = pq.top().second.second;
	// 	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&[place, value] : neighbors[node]) pq.push({c - value, {place, 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