Submission #683286

#	Time	Username	Problem	Language	Result	Execution time	Memory
683286		yogesh_sane	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	857 ms	262144 KiB

commuter_pass

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <climits>
using namespace std;
int n, m, s, t, u, v;
vector<vector<int>>parents;
vector<vector<int>>paths;
vector<int>path;
void dfs(int node){
    path.push_back(node);
    if(node == s){
        paths.push_back(path);
    }else{
        for(auto p : parents[node]){
            dfs(p);
        }
    }
    path.pop_back();
}

int main() {
    cin >> n >> m >> s >> t >> u >> v;
    vector<vector<pair<int, int>>> adj(n+1);
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    priority_queue<pair<long long,int>> q;
    vector<long long> dist(n+1, LONG_LONG_MAX);
    parents = vector<vector<int>>(n+1);
    vector<bool> visited(n+1);
    parents[s].push_back(s);
    dist[s] = 0;
    q.push({0,s});
    while(!q.empty()){
        pair<long long, int> a = q.top();
        q.pop();
        if(visited[a.second])
            continue;
        visited[a.second] = true;
        for(auto edge : adj[a.second]){
            int b = edge.first;
            int weight = edge.second;
            if(dist[a.second] + weight < dist[b]){
                dist[b] = dist[a.second] + weight;
                parents[b].clear();
                parents[b].push_back(a.second);
                q.push({-dist[b],b});
            }else if(-a.first + weight == dist[b]){
                parents[b].push_back(a.second);
            }
        }
    }
    dfs(t);
    long long ans = LONG_LONG_MAX;
    for(int i = 0; i < paths.size(); i++){
        vector<int> sp = paths[i];
        vector<vector<pair<int,int>>> adj2 = adj;
        for(int j = 1; j < sp.size(); j++){
            for(int k = 0; k < adj2[sp[j]].size(); k++){
                if(adj2[sp[j]][k].first == sp[j-1])
                    adj2[sp[j]][k].second = 0;
            }
            for(int k = 0; k < adj2[sp[j-1]].size(); k++){
                if(adj2[sp[j-1]][k].first == sp[j])
                    adj2[sp[j-1]][k].second = 0;
            }
        }

        vector<long long> dist2(n+1, LONG_LONG_MAX);    
        vector<bool> visited2(n+1, false);    
        dist2[u] = 0;
        q.push({0,u});
        while(!q.empty()){
            pair<long long, int> a = q.top();
            q.pop();
            if(visited2[a.second])
                continue;
            visited2[a.second] = true;    
            for(auto edge : adj2[a.second]){
                int b = edge.first;
                int weight = edge.second;
                if(dist2[a.second] + weight < dist2[b]){
                    dist2[b] = dist2[a.second] + weight;
                    q.push({-dist2[b],b});
                }
            }
        }
        ans = min(ans,dist2[v]);

    }
    cout << ans << '\n';
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:60:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int i = 0; i < paths.size(); i++){
      |                    ~~^~~~~~~~~~~~~~
commuter_pass.cpp:63:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for(int j = 1; j < sp.size(); j++){
      |                        ~~^~~~~~~~~~~
commuter_pass.cpp:64:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |             for(int k = 0; k < adj2[sp[j]].size(); k++){
      |                            ~~^~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:68:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |             for(int k = 0; k < adj2[sp[j-1]].size(); k++){
      |                            ~~^~~~~~~~~~~~~~~~~~~~~~

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