Submission #679309

#	Time	Username	Problem	Language	Result	Execution time	Memory
679309		hotboy2703	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	362 ms	28624 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],distv[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});
            }
        }
    }
}
bool in[100100];
long long dp[2][100100];
void dfs(long long u){
    dp[0][u] = distu[u];
    dp[1][u] = distv[u];
    in[u] = 1;
    for (auto v:g[u]){
        if (dists[v.first] + v.second == dists[u]){
            if (!in[v.first]){
                dfs(v.first);
            }
            dp[0][u] = min(dp[0][u],dp[0][v.first]);
            dp[1][u] = min(dp[1][u],dp[1][v.first]);
        }
    }
}
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(distu,u);
    dijkstra(distv,v);
    dfs(t);
    long long ans = distu[v];
    for (long long i = 1;i <= n;i ++){
        if (in[i]){
            ans = min(ans,dp[0][i] + distv[i]);
            ans = min(ans,dp[1][i] + distu[i]);
        }
    }
    cout<<ans<<'\n';
    return 0;
}

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