USACO 4.1 Fence Loops

The problem is to find smallest loops in a DAG. The idea is simple: each loop must have a start vertex and an end vertex. Since no loop connects to itself as the problem stated, the start and end vertex must be different. Also, the smallest perimeter of such a loop is the shortest path between the start vertex and end vertex, plus the length of the edge between two vertices. So to find the loop with smallest perimeter, we can iterate through each edge, calculate the shortest distance between two vertices that connect the edge (without considering the edge itself, of course, otherwise the shortest distance between two vertices would be the edge itself.), then add length of the edge. Do this for all possible edge and we get the result. The shortest distance between two vertices can be calculated using Dijkstra algorithm I posted earlier.

The pain point here is to properly transfer the source data to the graph representation. Here the transformation is done through state encoding (each vertex can be uniquely identified by the edge id it connects to). The overall code is a little bit bloated due to this.

#include <vector>
#include <iostream>
#include <fstream>
#include <queue>
#include <map>
#include <set>
#include <climits>

using namespace std;

// [to node index, edge weight] pair.
typedef std::pair<int, int> edge;
// [node index, distance to source] pair.
typedef std::pair<int, int> element;

map<set<int>, int> vxts;
int vxtCnt = 0;
set<int> vs;
ifstream fin("fence6.in");
ofstream fout("fence6.out");
vector<vector<edge>> graph;

int N, s, Ls, N1s, N2s;

int getVertexId(int Ns) {
    vs.clear(); vs.insert(s);
    for (int j = 0; j < Ns; ++j) {
        int sn; fin >> sn;
        vs.insert(sn);
    }
    auto iter = vxts.find(vs);
    if (iter == vxts.end()) {
        vxts[vs] = vxtCnt++;
        return vxts[vs];
    } else {
        return iter->second;
    }
}

void genGraph() {
    fin >> N;
    map<int, vector<edge>> g;
    for (int i = 0; i < N; ++i) {
        fin >> s >> Ls >> N1s >> N2s;
        int vtx1 = getVertexId(N1s);
        int vtx2 = getVertexId(N2s);
        g[vtx1].emplace_back(make_pair(vtx2, Ls));
        g[vtx2].emplace_back(make_pair(vtx1, Ls));
    }
    graph = vector<vector<edge>>(vxtCnt, vector<edge>());
    for (int i = 0; i < vxtCnt; ++i) {
        graph[i] = g[i];
    }
}

class compare {
public:
    bool operator()(const element&a, const element &b) {
        return a.second > b.second;
    }
};

int dijkstra(const vector<vector<edge>> &graph, int source, int target) {
    int size = (int)graph.size();
    if (!size) return -1;
    if (source < 0 || source >= size || target < 0 || target >= size)
        return -1;
    vector<bool> visited(size, false);
    vector<int> distance(size, INT_MAX);
    vector<int> prev(size, -1);
    distance[source] = 0;
    priority_queue<element, vector<element>, compare> pq;
    pq.emplace(make_pair(source, 0));
    while (!pq.empty()) {
        int v = pq.top().first;
        pq.pop();
        if (v == target) return distance[v];
        if (visited[v]) continue;
        for (auto &edge : graph[v]) {
            int u = edge.first; // vertice u that connects to v.
            int w = edge.second; // weight of edge that connects u and v.
            if (visited[u]) continue;
            if (distance[v] < distance[u] - w) {
                distance[u] = distance[v] + w;
                pq.emplace(make_pair(u, distance[u]));
            }
        }
        visited[v] = true;
    }
    return -1;
}

int main() {
    genGraph();
    int ans = INT_MAX;
    for (int i = 0; i < vxtCnt; ++i) {
        for (auto &e1 : graph[i]) {
            int w = e1.second;
            int to = e1.first;
            edge *e2;
            for (int j = 0; j < graph[to].size(); ++j) {
                if (graph[to][j].first == i) {
                    e2 = &graph[to][j];
                    break;
                }
            }
            e1.second = INT_MAX;
            e2->second = INT_MAX;
            int p = dijkstra(graph, i, to);
            if (p != -1 && p + w < ans) {
                ans = p + w;
            }
            e1.second = w;
            e2->second = INT_MAX;
        }
    }
    cout << ans << endl;
    fout << ans << endl;
}