제출 #1192534

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1192534		jbn8	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	669 ms	327680 KiB

commuter_pass

#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <functional>
#include <cassert>
using namespace std;
#define int long long
int N, M;
int S, T;
int U, V;
#define assert_in(a)assert(a < N);assert(a >= 0);
#define Qnode priority_queue<Node, vector<Node>, greater<Node>>
vector<map<int, int>> G;
class Node{
public:
    int cost, node, from;
    bool used=false;
    const bool operator>(const Node& o) const{
        return cost > o.cost;
    }
    const bool operator>=(const Node& o) const{
        return cost >= o.cost;
    }
    const bool operator<=(const Node& o) const{
        return cost <= o.cost;
    }
    const bool operator<(const Node& o) const{
        return cost < o.cost;
    }
};
vector<bool> is_solut;
vector<bool> is_in_solut(vector<vector<int>> G, int node){
    vector<bool> visited(N, false);
    function<void(int)> dfs;
    dfs = [&](int node){
        if(visited[node])return;
        visited[node] = true;
        for(int next_node:G[node]){
            if(next_node == -1)continue;
            if(!visited[next_node])
                dfs(next_node);
        }
    };
    dfs(node);
    return visited;
}
void add_recurs(Qnode* Q, vector<vector<int>>& G, Node node, vector<bool>& visited){
    for(int next_node:G[node.node]){
        if(!visited[next_node*2+1] && is_solut[next_node]){
            //visited[next_node*2+1] = true;
            Node cur={node.cost, next_node, node.node, true};
            Q->push(cur);
            add_recurs(Q, G, cur, visited);
            //visited[next_node*2+1] = false;
        }
    }
}
signed main(){
    cin >> N >> M;
    cin >> S >> T;
    cin >> U >> V;
    S--, U--, T--, V--;
    G = vector<map<int, int>>(N);
    assert_in(S);assert_in(T);
    assert_in(U);assert_in(V);
    for(int i=0; i<M; i++){
        int node0, node1, cost;
        cin >> node0 >> node1 >> cost;
        node0--, node1--;
        assert_in(node0);assert_in(node1);
        G[node0][node1] = cost;
        G[node1][node0] = cost;
    }
    Qnode Q;
    vector<int> S_T(N, -1);
    vector<vector<int>> S_Tup(N);
    vector<vector<int>> S_Tdown(N);
    Q.push({0, S, -1});
    while(!Q.empty()){
        Node cur=Q.top();
        Q.pop();
        assert_in(cur.node);
        //cout << cur.node << ' ' << cur.from << ' ' << cur.cost << '\n';
        if(S_T[cur.node] != -1){
            if(S_T[cur.node] == cur.cost && cur.from != -1){
                S_Tup[cur.node].push_back(cur.from);
                S_Tdown[cur.from].push_back(cur.node);
            }
            continue;
        }
        //if(cur.node == T)break;
        S_T[cur.node] = cur.cost;
        if(cur.from != -1){
            S_Tup[cur.node].push_back(cur.from);
            S_Tdown[cur.from].push_back(cur.node);
        }
        for(auto A:G[cur.node]){
            if(S_T[A.first] == -1)
                Q.push({cur.cost+A.second, A.first, cur.node});
        }
    }
    Qnode Q2;
    is_solut = is_in_solut(S_Tup, T);
    vector<bool> U_V(N*2, false);
    /*int temp=0;
    for(vector<int> A:S_Tup){
        cout << temp << " :";
        for(int n:A)cout << ' ' << n;
        cout << '\n';
        temp++;
    }
    cout << '\n';
    temp = 0;
    for(vector<int> A:S_Tdown){
        cout << temp << " :";
        for(int n:A)cout << ' ' << n;
        cout << '\n';
        temp++;
    }
    for(int t:is_solut)cout << t << ' ';
    cout << '\n';*/
    Q2.push({0, U, -1, false});
    while(!Q2.empty()){
        Node cur=Q2.top();
        Q2.pop();
        assert_in(cur.node);
        //cout << cur.node << ' ' << cur.from << ' ' << cur.cost << ' ' << cur.used << '\n';
        int key = cur.node*2+cur.used;
        if(cur.node == V){
            cout << cur.cost << '\n';
            break;
        };
        if(U_V[key])
            continue;
        U_V[key] = true;
        for(auto A:G[cur.node]){
            if(!U_V[A.first*2+cur.used])
                Q2.push({cur.cost+A.second, A.first, cur.node, cur.used});
        }
        if(!cur.used && is_solut[cur.node]){
            add_recurs(&Q2, S_Tup, cur, U_V);
            add_recurs(&Q2, S_Tdown, cur, U_V);
        }
    }
}

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