Submission #381312

#	Time	Username	Problem	Language	Result	Execution time	Memory
381312		oleksg	Commuter Pass (JOI18_commuter_pass)	C++11	31 / 100	748 ms	42156 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 used2[100001][2];
ll dist2[100001][2];
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> freeconsfor[100001];
vector<con> freeconsback[100001];

struct node{
    ll dist;
    ll cur;
    ll dir;
    bool operator<(const node& y) { return dist < y.dist; }
};

bool Compare(node a, node b)
{
    return a.dist > b.dist;
}

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){
        ll curdist = q.top().first * -1;
        ll 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]){
                freeconsfor[x].push_back({it, 0});
                freeconsback[it].push_back({x, 0});
                //cout << x << " " << it << " " << "free\n";
            }
        }
    }
    //dijkstra part 2, this time we know what the free cons are
    priority_queue<node, vector<node>, function<bool(node a, node b)>> qs(Compare);
    for (int x = 0; x < n; x++){
        dist2[x][0] = 1e15;
        dist2[x][1] = 1e15;
        used2[x][0] = -1;
        used2[x][1] = -1;
    }
    qs.push({0, u, 0});
    qs.push({0, u, 1});
    dist2[u][0] = 0;
    dist2[u][1] = 0;
    while(qs.size() > 0){
        ll curdist = qs.top().dist;
        ll cur = qs.top().cur;
        ll dir = qs.top().dir;
        qs.pop();
        if (used2[cur][dir] == -1){
            used2[cur][dir] = 1;
            //cout << "yes\n";
            for (auto next: cons[cur]){
                if (dist2[next.des][dir] > dist2[cur][dir] + next.w){
                    dist2[next.des][dir] = dist2[cur][dir] + next.w;
                    qs.push({dist2[next.des][dir], next.des, dir});
                }
            }
            if (dir == 0){
                for (auto next: freeconsfor[cur]){
                    if (dist2[next.des][dir] > dist2[cur][dir] + next.w){
                        dist2[next.des][dir] = dist2[cur][dir] + next.w;
                        qs.push({dist2[next.des][dir], next.des, dir});
                    }
                }
            }
            else{
                for (auto next: freeconsback[cur]){
                    if (dist2[next.des][dir] > dist2[cur][dir] + next.w){
                        dist2[next.des][dir] = dist2[cur][dir] + next.w;
                        qs.push({dist2[next.des][dir], next.des, dir});
                    }
                }
            }
        }
    }
    cout << min(dist2[v][0], dist2[v][1]) << "\n";

}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:85:12: warning: unused variable 'curdist' [-Wunused-variable]
   85 |         ll curdist = q.top().first * -1;
      |            ^~~~~~~
commuter_pass.cpp:127:12: warning: unused variable 'curdist' [-Wunused-variable]
  127 |         ll curdist = qs.top().dist;
      |            ^~~~~~~

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