PROBLEM LINK:
Author: Bumjun Kim
Tester: Jatin Yadav
Editorialist: Bumjun Kim
DIFFICULTY:
Medium
PREREQUISITES:
Dijkstra, Bitmask
PROBLEM:
You are given a graph with N vertices and E edges with some vertices containing keys that lock other vertices. Find the shortest path from vertex 1 to vertex N.
Subtask 1 [30 points]: N \leq 20000, E \leq 100000, K = 0
Subtask 2 [30 points]: N \leq 10000, E \leq 20000, K \leq 6
Subtask 3 [40 points]: N \leq 100000, E \leq 200000, K \leq 12
EXPLANATION:
Subtask 1:
In this subtask, there are 0 keys which means that standard Dijkstra passes the subtask. This solution runs in O(ELogE).
Subtask 2:
For this subtask, there are up to 6 keys. It is possible to have a 2D array with dimensions 2^6 and 10000 which stores the subsets of the keys taken and the vertex. Dijkstra can be performed on the new set of vertices which passes the subtask. This algorithm runs in O(2^6*ELog(E*2^6))
Subtask 3:
For this subtask, there are up to 12 keys. It is possible to see that the only nodes with importance are the starting and ending nodes and nodes with either keys or nodes that are locked. Dijkstra can be run from these nodes in order to create a compressed version of the graph. The solution used in subtask 2 can now be used on the compressed graph which passes the subtask. This solution runs in O(24*ELogE).
SOLUTIONS:
Setter's Solution
#include "bits/stdc++.h"
using namespace std;
int main() {
long long n, e, k;
cin >> n >> e >> k;
bool impcheck[n+1];
memset(impcheck, 0, sizeof impcheck);
vector<pair<long long, long long> > adj[n+1];
vector<long long> imp;
imp.push_back(1);
imp.push_back(n);
impcheck[1] = true;
impcheck[n] = true;
for (long long i=0; i<e; i++) {
long long a, b, c;
cin >> a >> b >> c;
adj[a].push_back(make_pair(b, c));
adj[b].push_back(make_pair(a, c));
}
vector<pair<long long, long long> > lpairs;
long long addmask[n+1];
memset(addmask, 0, sizeof addmask);
long long needmask[n+1];
memset(needmask, 0, sizeof needmask);
for (long long i=0; i<k; i++) {
long long a, b;
cin >> a >> b;
lpairs.push_back(make_pair(a, b));
imp.push_back(a);
imp.push_back(b);
addmask[a] |= (1<<i);
needmask[b] |= (1<<i);
impcheck[a] = true;
impcheck[b] = true;
}
long long su = imp.size();
vector<pair<long long, long long> > comp[su+1];
long long addmaskc[su];
long long needmaskc[su];
memset(addmaskc, 0, sizeof addmaskc);
memset(needmaskc, 0, sizeof needmaskc);
for (long long RT=0; RT<imp.size(); RT++) {
long long sr = imp[RT];
long long distance[n+1];
for (long long i=0; i<n+1; i++) distance[i] = LLONG_MAX;
priority_queue<pair<long long, long long>, vector<pair<long long, long long> >, greater<pair<long long, long long> > > proc;
proc.push(make_pair(0, sr));
addmaskc[RT] = addmask[imp[RT]];
needmaskc[RT] = needmask[imp[RT]];
while (!proc.empty()) {
pair<long long, long long> r = proc.top(); proc.pop();
long long no = r.second, di = r.first;
if (distance[no] < di) continue;
distance[no] = di;
if (impcheck[no] && no != sr) continue;
for (long long i=0; i<adj[no].size(); i++) {
long long ot = adj[no][i].first;
long long od = di + adj[no][i].second;
if (distance[ot] > od) {
distance[ot] = od;
proc.push(make_pair(od, ot));
}
}
}
for (long long i=0; i<imp.size(); i++) {
if (i != RT) {
long long to = imp[i];
if (distance[to] == LLONG_MAX) continue;
comp[RT].push_back(make_pair(i, distance[to]));
}
}
}
long long dist[su+1][(1<<k)];
for (long long i=0; i<su+1; i++) for (long long j=0; j<(1<<k); j++) dist[i][j] = LLONG_MAX;
priority_queue<pair<long long, pair<long long, long long> > > proc; // dist, mask, node
proc.push(make_pair(0, make_pair(0, 0)));
long long mn = LLONG_MAX;
while (!proc.empty()) {
pair<long long, pair<long long, long long> > fi = proc.top(); proc.pop();
long long di = fi.first;
long long no = fi.second.second;
long long ma = fi.second.first | addmaskc[no];
if (dist[no][ma] < di) continue;
dist[no][ma] = di;
if (no == 1) {
mn = min(mn, di);
}
for (long long i=0; i<comp[no].size(); i++) {
long long ot = comp[no][i].first;
long long dis = di + comp[no][i].second;
if ((ma | needmaskc[ot]) == ma) {
if (dist[ot][ma] > dis) {
dist[ot][ma] = dis;
proc.push(make_pair(dis, make_pair(ma, ot)));
}
}
}
}
if (mn == LLONG_MAX) cout << -1 << endl;
else cout << mn << endl;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sd(x) scanf("%d", &(x))
#define pii pair<int, int>
#define F first
#define S second
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())
#define ld long double
template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
os<<"("<<p.first<<", "<<p.second<<")";
return os;
}
template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
os<<"{";
for(int i = 0;i < (int)v.size(); i++){
if(i)os<<", ";
os<<v[i];
}
os<<"}";
return os;
}
#ifdef LOCAL
#define cerr cout
#else
#endif
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
const ll INF = 1e16 + 61;
const int N = 100005;
const int K = 30;
ll D[K][K];
int ulta[N];
struct graph{
int n;
vector<vector<pair<int, ll>>> con;
void add_edge(int u, int v, ll c, bool bidirectional = true){
con[u].push_back({v, c});
if(bidirectional) con[v].push_back({u, c});
}
graph(int n) : n(n), con(n + 1){};
vector<ll> dijkstra(int s, bool allow_locked = 0){
priority_queue<pair<ll, int>,vector<pair<ll, int>>, greater<pair<ll, int>> > Q;
vector<ll> dist(n + 1, INF);
dist[s] = 0;
Q.push(pair<ll, int>(0LL,s));
while(!Q.empty()) {
pair<ll, int> top = Q.top();
Q.pop();
int v = top.second;
ll d = top.first;
if(d <= dist[v]) {
for(auto it : con[v]){
int v2 = it.first;
ll cost = it.second;
if(dist[v2] > dist[v] + cost) {
dist[v2] = dist[v] + cost;
if(!allow_locked && ulta[v2]) continue;
Q.push(pair<ll, int>(dist[v2], v2));
}
}
}
}
return dist;
}
};
int locked[K];
// O(k^2 * 2^k + k * |E|)
int main(){
int n, m, k; sd(n); sd(m); sd(k);
graph g(n);
for(int i = 1; i <= m; i++){
int u, v, c;
sd(u); sd(v); sd(c);
g.add_edge(u, v, c);
}
locked[0] = 1;
locked[2 * k + 1] = n;
for(int i = 1; i <= k; i++){
int p, q; sd(p); sd(q);
assert(p != q);
locked[i] = q;
locked[i + k] = p;
ulta[q] = i;
}
for(int i = 0; i <= 2 * k + 1; i++){
vector<ll> d = g.dijkstra(locked[i]);
for(int j = 0; j <= 2 * k + 1; j++){
D[i][j] = d[locked[j]];
}
}
graph g2((2 * k + 2) << k);
for(int i = 0; i <= 2 * k + 1; i++){
for(int mask = 0; mask < (1 << k); mask++){
int node = (i << k) + mask;
for(int j = 0; j <= 2 * k + 1; j++) if(j != i){
if(ulta[locked[j]] && !(mask >> (ulta[locked[j]] - 1) & 1)) continue;
int node2 = (j << k) + (mask | ( (j > k && j <= 2 * k) ? (1 << (j - k - 1)) : 0));
g2.add_edge(node, node2, D[i][j], 0);
}
}
}
vector<ll> d = g2.dijkstra(0, 1);
ll ret = INF;
for(int mask = 0; mask < (1 << k); mask++) ret = min(ret, d[((2 * k + 1) << k) + mask]);
printf("%lld\n", ret >= INF ? -1 : ret);
}