제출 #1314702

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1314702		mikolajsz	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	282 ms	22040 KiB

commuter_pass

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAXN = 1e5+1;
const int MAXM = 2e5+1;
const long long inf = 1e18;

int N,M,S,T,U,V;
vector<pair<long long, long long>> G[MAXN];
vector<long long> distuv[2],distst[2],bestu[2],bestv[2];

vector<long long> dijkstra(int start){
    vector<long long> dist(N+1,inf);
    dist[start]=0;
    priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>> pq;
    pq.push({dist[start],start});
    while(!pq.empty()){
        auto p = pq.top(); pq.pop();
        long long d = p.first, v = p.second;
        if(d!=dist[v]) continue;
        for(auto e: G[v]){
            long long u=e.first,w=e.second;
            if(d+w<dist[u]){
                dist[u]=d+w;
                pq.push({dist[u],u});
            }
        }
    }
    return dist;
}

vector<long long> dijkstra2(int start, int whichst, int whichuv){
    vector<long long> best(N+1,inf);
    priority_queue<array<long long, 3>, vector<array<long long, 3>>, greater<array<long long, 3>>> pq;
    pq.push({0,start,distuv[whichuv][start]});
    while(!pq.empty()){
        auto p = pq.top(); pq.pop();
        long long d = p[0], v = p[1], bestuv = p[2];
        if(d+distst[whichst^1][v]!=distst[0][T]) continue;
        if(bestuv>=best[v]) continue;
        best[v]=bestuv;
        for(auto e: G[v]){
            long long u=e.first,w=e.second;
            long long newdist = d+w;
            if(newdist + distst[whichst^1][u]!=distst[0][T]) continue;
            long long nb = min(bestuv,distuv[whichuv][u]);
            pq.push({newdist,u,nb});
        }
    }
    return best;
}

void solve(){
    cin >> N >> M >> S >> T >> U >> V;
    for(int i=0; i<M; i++){
        long long a,b,w; cin >> a >> b >> w;
        G[a].push_back({b,w});
        G[b].push_back({a,w});
    }
    distst[0] = dijkstra(S); 
    distst[1] = dijkstra(T); 
    distuv[0] = dijkstra(U); 
    distuv[1] = dijkstra(V); 
    bestu[0]=dijkstra2(S,0,0);
    bestu[1]=dijkstra2(T,1,0);
    bestv[0]=dijkstra2(S,0,1);
    bestv[1]=dijkstra2(T,1,1);
    long long ans = distuv[0][V];
    for(int i=1; i<=N; i++){
        long long b1 = distuv[0][i]+min(bestv[0][i],bestv[1][i]);
        long long b2 = distuv[1][i]+min(bestu[0][i],bestu[1][i]);
        //cout << i << " " << b1 << " " << b2 << "xd\n";
        ans=min(ans,min(b1,b2));
    }
    cout << ans << "\n";
} 
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int t=1;
	//cin>>t;
	while(t--)
		solve();
}

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