Submission #683260

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

commuter_pass

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

int main() {
    int n, m, s, t, u, v;
    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);
    vector<vector<int>> parents(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;
      	if(a.second == t)
          continue;
        for(auto edge : adj[a.second]){
            int b = edge.first;
            int weight = edge.second;
            if(-a.first + weight < dist[b]){
                dist[b] = -a.first + 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);
            }
        }
    }
    queue<int> parentq;
    for(auto p : parents[t])
        parentq.push(p);
    vector<bool> sp(n+1);
    sp[t] = true;
    while(!parentq.empty()){
        int p = parentq.front();
        parentq.pop();
        sp[p] = true;
        for(auto gp : parents[p])
            if(gp != p)
                parentq.push(gp);
    }
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < adj[i].size(); j++){
            if(sp[i] && sp[adj[i][j].first])
                adj[i][j].second = 0;
        }
    }
    vector<long long> dist2(n+1, LONG_LONG_MAX);    
    vector<bool> visited2(n+1);    
    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;    
      	if(a.second == v)
          continue;
        for(auto edge : adj[a.second]){
            int b = edge.first;
            int weight = edge.second;
            if(-a.first + weight < dist2[b]){
                dist2[b] = -a.first + weight;
                q.push({-dist2[b],b});
            }
        }
    }
    cout << dist2[v] << '\n';
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:59:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for(int j = 0; j < adj[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~

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