Submission #381180

#	Time	Username	Problem	Language	Result	Execution time	Memory
381180		oleksg	Commuter Pass (JOI18_commuter_pass)	C++11	31 / 100	568 ms	35804 KiB

commuter_pass

#pragma GCC optimize("O2")
#include <fstream>
#include <string>
#include <iostream>
#include <bitset>
#include <math.h>
#include <string>
#include <algorithm>
#include <assert.h>
#include <bits/stdc++.h>
#include <vector>
#include <queue>
#include<stdio.h>
#include<ctype.h>
#define ll long long
using namespace std;

struct con{
    ll des;
    ll w;
};

ll n, m;

ll s, t;

ll u, v;

ll dist[100001];
ll used[100001];
ll keep[100001];
// keep track of all the nodes going to us that can reach us in the minimum distance, later updated to only be nodes that go to us however we also gotta be a usable node that leads back to t
vector<ll> tous[100001];


vector<con> cons[100001];

vector<con> freecons[100001];
void dfs(int cur){
    keep[cur] = 1;
    for (auto it: tous[cur]){
        if (keep[it] == -1){
            keep[it] = 1;
            dfs(it);
        }
    }
}
int main(){
    cin >> n >> m >> s >> t >> u >> v;
    s -= 1;
    t -= 1;
    u -= 1;
    v -= 1;
    ll one, two, three;
    for (int x = 0; x < m; x++){
        cin >> one >> two >> three;
        cons[one - 1].push_back({two - 1, three});
        cons[two - 1].push_back({one - 1, three});
    }
    for (int x = 0; x < n; x++){
        dist[x] = 1e15;
        used[x] = -1;
        keep[x] = -1;
    }
    priority_queue<pair<ll, ll>> q;
    dist[s] = 0;
    q.push({0, s});
    while(q.size() > 0){
        int curdist = q.top().first * -1;
        int cur = q.top().second;
        q.pop();
        if (used[cur] == -1){
            used[cur] = 1;
            for (auto next: cons[cur]){
                if (dist[next.des] > dist[cur] + next.w){
                    dist[next.des] = dist[cur] + next.w;
                    tous[next.des].clear();
                    tous[next.des].push_back(cur);
                    q.push({-1*dist[next.des], next.des});
                }
                else if (dist[next.des] == dist[cur] + next.w){
                    //partial update
                    tous[next.des].push_back(cur);
                }
            }
        }
    }
    dfs(t);
    for (int x = 0; x < n; x++){
        if (keep[x] == 1){
            for (auto it: tous[x]){
                freecons[x].push_back({it, 0});
                freecons[it].push_back({x, 0});
                //cout << x << " " << it << " " << "free\n";
            }
        }
    }
    //dijkstra part 2, this time we know what the free cons are
    for (int x = 0; x < n; x++){
        dist[x] = 1e15;
        used[x] = -1;
    }
    q.push({0, u});
    dist[u] = 0;
    while(q.size() > 0){
        int curdist = q.top().first * -1;
        int cur = q.top().second;
        q.pop();
        if (used[cur] == -1){
            used[cur] = 1;
            for (auto next: cons[cur]){
                if (dist[next.des] > dist[cur] + next.w){
                    dist[next.des] = dist[cur] + next.w;
                    q.push({-1*dist[next.des], next.des});
                }
            }
            for (auto next: freecons[cur]){
                if (dist[next.des] > dist[cur] + next.w){
                    dist[next.des] = dist[cur] + next.w;
                    q.push({-1*dist[next.des], next.des});
                }
            }
        }
    }
    cout << dist[v] << "\n";

}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:69:13: warning: unused variable 'curdist' [-Wunused-variable]
   69 |         int curdist = q.top().first * -1;
      |             ^~~~~~~
commuter_pass.cpp:106:13: warning: unused variable 'curdist' [-Wunused-variable]
  106 |         int curdist = q.top().first * -1;
      |             ^~~~~~~

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