USACO FEB09 Problem 'revamp' Analysis

by John Pardon

Define the K-modified length of a path to be the sum of the lengths of all but its K longest edges. For example, the 0-modified length of a path is just its length. One way of rephrasing the problem is that we need to calculate the shortest K-modified length among all paths from vertex 1 to vertex N. [NB: from the sample input and output, it is clear that this is NOT necessarily equal to the K-modified length of the regular shortest path from 1 to N].

From the given graph (V,E), construct a new graph as follows. The vertex set will be V x {0,1,2,...,K}. For each edge e=(v1,v2) of length L, add 2K+1 edges as follows:

* add an edge from (v1,k) to (v2,k) of length L for all k in {0,1,2,...,K}

* add an edge from (v1,k) to (v2,k+1) of length 0 for all k in {0,1,2,...,K-1}

Also add edges from (v,k) to (v,k+1) of length 0 for all v and for all k in {0,1,2,...,K-1}. It is left as an exercise to the reader to convince him/herself that the length of the shortest path from (1,0) to (N,K) in this modified graph is equal to the shortest K-modified length among paths from 1 to N in the original graph.

This new graph has O(VK) vertices and O(EK) edges, so since Dijkstra's algorithm is O(e log v), the above algorithm runs in O(E K log V), which should run in time.

Code by Bruce Merry follows:

/*
PROG: revamp
LANG: C++
*/

#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

typedef long long ll;

#define SZ(x) (int((x).size()))

struct qitem
{
    int v;
    int k;
    ll p;

    qitem() {}
    qitem(int v, int k, ll p) : v(v), k(k), p(p) {}

    bool operator <(const qitem &q) const
    {
        return p > q.p;
    }
};

struct edge
{
    int trg;
    int cost;

    edge() {}
    edge(int t, int c) : trg(t), cost(c) {}
};


int main()
{
    ifstream in("revamp.in");
    ofstream out("revamp.out");
    int N, M, K;
    vector<vector<edge> > edges;

    in >> N >> M >> K;
    edges.resize(N);
    for (int i = 0; i < M; i++)
    {
        int a, b, c;
        in >> a >> b >> c;
        a--;
        b--;
        edges[a].push_back(edge(b, c));
        edges[b].push_back(edge(a, c));
    }

    priority_queue<qitem> q;
    ll prio[N][K + 1];
    for (int i = 1; i < N; i++)
        for (int j = 0; j <= K; j++)
            prio[i][j] = LONG_LONG_MAX;
    for (int j = 0; j <= K; j++)
    {
        prio[0][j] = 0LL;
        q.push(qitem(0, j, 0LL));
    }

    while (!q.empty())
    {
        qitem c = q.top();
        q.pop();
        if (prio[c.v][c.k] != c.p)
            continue;

        for (int i = 0; i < SZ(edges[c.v]); i++)
        {
            int nxtv = edges[c.v][i].trg;
            int nxtk = c.k;
            ll nxtp = c.p + edges[c.v][i].cost;
            if (nxtp < prio[nxtv][nxtk])
            {
                prio[nxtv][nxtk] = nxtp;
                q.push(qitem(nxtv, nxtk, nxtp));
            }

            if (nxtk < K)
            {
                nxtk++;
                nxtp = c.p;
                if (nxtp < prio[nxtv][nxtk])
                {
                    prio[nxtv][nxtk] = nxtp;
                    q.push(qitem(nxtv, nxtk, nxtp));
                }
            }
        }
    }

    out << prio[N - 1][K] << "\n";

    return 0;
}