Synchronous Shopping solution

sync_shoping.cpp

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <list>
#include <bitset>
using namespace std;

struct State {
    int p, l, f;
    State(int pin, int lin, int fin) : p(pin), l(lin), f(fin) {}
};

bool operator < (const State& l, const State& r) {
    return l.l > r.l;
}

void visit(vector< list< pair<int, int> > >& adj, vector<int>& fishMask, vector<vector<int>>& res) {
    priority_queue<State> pq;
    pq.push( State(0, 0, fishMask[0]) );
    while (!pq.empty()) {
        State s = pq.top(); pq.pop();
        if (s.l < res[s.p][s.f]) {
            res[s.p][s.f] = s.l;
            for (auto v : adj[s.p]) {
                pq.push( State(v.first, s.l + v.second, s.f | fishMask[v.first]) );
            }
        }
    }
}

int main() {
    int N, M, T;
    cin >> N >> M >> T;
    N; M; T;
    vector<int> fishMask(N, 0);
    for (int i = 0; i < N; ++i) {
        int n;
        cin >> n;
        while (n > 0) {
            int t;
            cin >> t;
            --t;
            fishMask[i] |= 1 << t;
            --n;
        }
    }
    
    vector< list< pair<int, int> > > adj(N);
    for (int i = 0; i < M; ++i) {
        int u,v,w;
        cin >> u >> v >> w;
        --u; --v;
        adj[u].push_back( make_pair(v, w) );
        adj[v].push_back( make_pair(u, w) );
    }
    int maxFishMask = 1<<(T);
    vector< vector<int> > res(N, vector<int>(maxFishMask, 1e6));
    visit(adj, fishMask, res);
    
    int minPath = 1e6;
    for (int i = 0; i < maxFishMask; ++i)
        for (int j = i; j < maxFishMask; ++j)
            if ((i | j) == maxFishMask-1) {
                minPath = min(minPath, max(res[N-1][i], res[N-1][j]));
            }       
    cout << minPath;
    
    return 0;
}