Submission #372964

#	Time	Username	Problem	Language	Result	Execution time	Memory
372964		ntabc05101	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	537 ms	23648 KiB

commuter_pass

#ifndef LOCAL
#define NDEBUG 1
#endif // LOCAL
#include<bits/stdc++.h>

#define i64 int64_t

const i64 inf=1e17;
const int max_n=100000;

std::vector< std::pair<int, int> > adjList[max_n];
i64 dist_u[max_n], dist_v[max_n], dist_s[max_n];
bool visited[max_n];
i64 dp[2][max_n];
i64 result;

void dijkstra(int start, i64 dist[]) {
        std::priority_queue< std::pair<i64, int> > pq;
        std::fill(dist, dist+max_n, inf);

        pq.push({-(dist[start]=0), start});
        while (!pq.empty()) {
                i64 cdist=-pq.top().first;
                int cvertex=pq.top().second;
                pq.pop();
                if (dist[cvertex]<cdist) {
                        continue;
                }

                for (auto& to: adjList[cvertex]) {
                        if (dist[to.first]>cdist+to.second) {
                                pq.push({-(dist[to.first]=cdist+to.second), to.first});
                        }
                }
        }
}

void dijkstra2(int start, int finish) {
        std::fill(dp[0], dp[0]+max_n, inf);
        std::fill(dp[1], dp[1]+max_n, inf);
        memset(visited, false, sizeof(visited));

        std::priority_queue< std::pair< i64, std::pair<int, int> > > pq;
        pq.push({0, {start, 0}});
        while (!pq.empty()) {
                i64 cdist=pq.top().first;
                int cvertex=pq.top().second.first;
                int cpar=pq.top().second.second;
                pq.pop();

                if (!visited[cvertex]) {
                        visited[cvertex]=true;
                        dist_s[cvertex]=-cdist;
                        dp[0][cvertex]=std::min(dist_u[cvertex], dp[0][cpar]);
                        dp[1][cvertex]=std::min(dist_v[cvertex], dp[1][cpar]);
                        
                        for (auto& to: adjList[cvertex]) {
                                pq.push({cdist-to.second, {to.first, cvertex}});
                        }
                }
                else {
                        if (std::min(dist_u[cvertex], dp[0][cpar])+std::min(dist_v[cvertex], dp[1][cpar])<=dp[0][cvertex]+dp[1][cvertex]) {
                                dp[0][cvertex]=std::min(dist_u[cvertex], dp[0][cpar]);
                                dp[1][cvertex]=std::min(dist_v[cvertex], dp[1][cpar]);
                        }
                }
        }
        /*while (!pq.empty()) {
                int cdist=-pq.top().first;
                int cvertex=pq.top().second.first;;
                int cpar=pq.top().second.second;
                pq.pop();

                if (dist_s[cvertex]<cdist) continue;

                for (auto& to: adjList[cvertex]) {
                        i64 new_dist=cdist+to.second;
                        if (dist_s[to.first]>new_dist) {
                                pq.push({-(dist_s[to.first]=new_dist), {to.first, cvertex}});
                                dp[0][cvertex]=std::min(dist_u[cvertex], dp[0][cpar]);
                                dp[1][cvertex]=std::min(dist_v[cvertex], dp[1][cpar]);
                        }
                        else {
                                if (dist_s[to.first]==new_dist and 
                                    std::min(dist_u[cvertex], dp[0][cpar])+std::min(dist_v[cvertex], dp[1][cpar])<=dp[0][cvertex]+dp[1][cvertex]) {
                                        dp[0][cvertex]=std::min(dist_u[cvertex], dp[0][cpar]);
                                        dp[1][cvertex]=std::min(dist_v[cvertex], dp[1][cpar]);
                                }
                        }
                }
        }*/

        result=std::min(result, dp[0][finish]+dp[1][finish]);
}

int main() {
        std::ios_base::sync_with_stdio(0); std::cin.tie(0);

        int n, m, s, t, u, v;
        std::cin>>n>>m>>s>>t>>u>>v;
        --s, --t, --u, --v;

        for (int i=0; i<m; ++i) {
                int a, b, c; std::cin>>a>>b>>c;
                --a, --b;

                adjList[a].push_back({b, c});
                adjList[b].push_back({a, c});
        }

        dijkstra(u, dist_u);
        dijkstra(v, dist_v);

        result=dist_u[v];

        dijkstra2(s, t);
        dijkstra2(t, s);

        std::cout<<result<<"\n";

        return 0;
}

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