Convex Hull (Dijkstra)

convex_hull.cpp

// solucao de Lúcio Cardoso

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2010;
const int MAXK = 210;
const int INF = 1e9+10;

typedef pair<int, int>pii;

int k, n, m, dist[MAXN][MAXK];
vector< pair<int, pii> > grafo[MAXN];
bool mark[MAXN];

void Dijkstra(int S, int x)
{
    for (int i = 1; i <= n; i++) dist[i][x] = INF;
    dist[S][x] = 0;
    priority_queue< pii, vector<pii>, greater<pii> > fila;
    fila.push(make_pair(0, S));

    int davez = -1;
    while (!fila.empty())
    {
        int atual = fila.top().second;
        fila.pop();
        if (!mark[atual])
            davez = atual, mark[atual] = 1;
        if (davez == -1) continue;

        for (int i = 0; i < grafo[davez].size(); i++)
        {
            int v = grafo[davez][i].second.first, d = grafo[davez][i].first;
            int hull = grafo[davez][i].second.second;

            if (hull >= x) continue;

            if (dist[v][x] > dist[davez][x-hull]+d)
            {
                dist[v][x] = dist[davez][x-hull]+d;
                fila.push(make_pair(dist[v][x], v));
            }
        }
    }
}

int main(void)
{
    ios_base::sync_with_stdio(false);
	cin.tie(0);

    cin >> k >> n >> m;

    while (m--)
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        grafo[a].push_back(make_pair(c, make_pair(b, d)));
        grafo[b].push_back(make_pair(c, make_pair(a, d)));
    }
    int x, y;
    cin >> x >> y;

    for (int i = 0; i <= k; i++)
    {
        memset(mark, 0, sizeof mark);
        Dijkstra(x, i);
    }

    if (dist[y][k] == INF)
        cout << "-1\n";
    else
        cout << dist[y][k] << "\n";
}