Submission #1115322

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115322		staszic_ojuz	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	405 ms	262144 KiB

commuter_pass

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
using namespace std;

struct State{
    long long v, dist;
    vector<long long> path;
};

bool comp(const State &s1, const State &s2){
    return s1.dist>s2.dist;
}

vector<vector<pair<long long, long long>>> graph;
vector<bool> found;
vector<pair<long long, long long>> freeEdges;

State Dijkstra(long long v1, long long v2, bool pathRecovery){
    for (long long i=0;i<found.size();i++) found[i]=false;
    priority_queue<State, vector<State>, bool (*)(const State &, const State &)> pq(comp);
    pq.push(State{v1, 0, vector<long long>{v1}});
    while (!pq.empty()){
        State sta=pq.top();
        pq.pop();
        found[sta.v]=true;
        if (sta.v==v2) return sta;
        for (long long i=0;i<graph[sta.v].size();i++){
            if (!found[graph[sta.v][i].first]){
                long long addedCost=graph[sta.v][i].second;
                if (graph[sta.v][i].first==freeEdges[sta.v].first||graph[sta.v][i].first==freeEdges[sta.v].second) addedCost=0;
                if (pathRecovery){
                    vector<long long> temp=sta.path;
                    temp.push_back(graph[sta.v][i].first);
                    pq.push(State{graph[sta.v][i].first, sta.dist+addedCost, temp});
                }
                else pq.push(State{graph[sta.v][i].first, sta.dist+addedCost, sta.path});
            }
        }
    }
    return State{-1, -1, vector<long long>{}};
}

void PathOut(State sta){
    freeEdges[sta.path[0]].second=sta.path[1];
    freeEdges[sta.path[sta.path.size()-1]].first=sta.path[sta.path.size()-2];
    for (long long i=1;i<sta.path.size()-1;i++){
        freeEdges[sta.path[i]].first=sta.path[i-1];
        freeEdges[sta.path[i]].second=sta.path[i+1];
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n, m, s, t, u, v;
    cin>>n>>m>>s>>t>>u>>v;
    graph.resize(n+7);
    found.resize(n+7);
    freeEdges.resize(n+7);
    for (long long i=0;i<m;i++){
        long long v1, v2, c;
        cin>>v1>>v2>>c;
        graph[v1].push_back({v2, c});
        graph[v2].push_back({v1, c});
    }
    PathOut(Dijkstra(s, t, true));
    long long dist=Dijkstra(u, v, false).dist;
    cout<<dist<<'\n';
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'State Dijkstra(long long int, long long int, bool)':
commuter_pass.cpp:21:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for (long long i=0;i<found.size();i++) found[i]=false;
      |                        ~^~~~~~~~~~~~~
commuter_pass.cpp:29:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for (long long i=0;i<graph[sta.v].size();i++){
      |                            ~^~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void PathOut(State)':
commuter_pass.cpp:48:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for (long long i=1;i<sta.path.size()-1;i++){
      |                        ~^~~~~~~~~~~~~~~~~~

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