leetcode-go/poj/1724.roads/main.cc

#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

const int K = 10000, R = 10000;
const int N = 100, L = 100, T = 100;
const int INF = 1 << 30;

int k, n, r, min_l;

// Save intermediate results for pruning,
// mid_l[i][j] means the min len at city i with coin j.
int mid_l[N + 1][K + 1];
bool flag[N + 1];

struct Path {
  int dst;
  int len;
  int cst;
  Path(int d, int l, int c) : dst(d), len(l), cst(c) {}
};

vector<Path> adj[N + 1];

void dfs(int i, int p, int coin) {
  if (i == n) {
    min_l = min(min_l, p);
    return;
  }
  if (min_l <= p) return;
  if (mid_l[i][coin] <= p)
    return;
  else
    mid_l[i][coin] = p;
  flag[i] = true;
  vector<Path> &vec = adj[i];
  for (int j = 0; j < vec.size(); j++) {
    if (flag[vec[j].dst] || coin < vec[j].cst) continue;
    dfs(vec[j].dst, p + vec[j].len, coin - vec[j].cst);
  }
  flag[i] = false;
};

int main() {
  scanf("%d %d %d", &k, &n, &r);
  for (int i = 0, s, d, l, t; i < r; i++) {
    scanf("%d %d %d %d", &s, &d, &l, &t);
    adj[s].push_back(Path(d, l, t));
  }
  min_l = INF;
  memset(flag, 0, sizeof(flag));
  memset(mid_l, 0x3F, sizeof(mid_l));
  dfs(1, 0, k);
  if (min_l == INF)
    printf("-1\n");
  else
    printf("%d\n", min_l);
  return 0;
}