제출 #678963

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
678963		hotboy2703	Commuter Pass (JOI18_commuter_pass)	C++14	31 / 100	439 ms	31868 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
long long n,m;
vector <pair <long long,long long> > g[100100];
vector <pair <long long,long long> > gg[100100];
long long dists[100100],distt[100100],distu[100100];
void dijkstra(long long dist[],long long s){
    memset(dist,0x3f, sizeof (long long) * (n + 10));
    dist[s] = 0;
    priority_queue <pair <long long,long long> ,vector <pair <long long,long long> > ,greater <pair <long long,long long > > >  q;
    for (long long i = 1;i <= n; i++){
        q.push({dist[i],i});
    }
    while (!q.empty()){
        long long u = q.top().second;
        long long val = q.top().first;
        q.pop();
        if (val != dist[u])continue;
        for (auto tmp:g[u]){
            long long v = tmp.first;
            long long len = tmp.second;
            if (dist[v] > dist[u] + len){
                dist[v] = dist[u] + len;
                q.push({dist[v],v});
            }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n>>m;
    long long s,t,u,v;
    cin>>s>>t>>u>>v;
    for (long long i = 1;i <= m;i ++){
        long long uu,vv,w;
        cin>>uu>>vv>>w;
        g[uu].push_back({vv,w});
        g[vv].push_back({uu,w});
    }
    dijkstra(dists,s);
    dijkstra(distt,t);
    for (long long i = 1;i <= n;i ++){
        gg[i] = g[i];
        for (auto &v:g[i]){
            if (min(dists[i] + v.second + distt[v.first],distt[i] + v.second + dists[v.first]) == dists[t] && dists[i] < dists[v.first]){
                v.second = 0;
            }
        }
    }
    dijkstra(distu,u);
    long long ans = distu[v];
    for (long long i = 1;i <= n;i ++){
        g[i] = gg[i];
        for (auto &v:g[i]){
            if (min(dists[i] + v.second + distt[v.first],distt[i] + v.second + dists[v.first]) == dists[t] && dists[i] > dists[v.first]){
                v.second = 0;
            }
        }
    }
    dijkstra(distu,u);
    ans = min(ans,distu[v]);
    cout<<ans<<'\n';
    return 0;
}

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