Отримання знань

   Входные данные

   Выходные данные

   Пример входных данных

   Пример выходных данных

   Анализ условия и обсуждение идеи решения

   Пример решения на Pascal:

program PKU1062;
{$S-,Q-,R-,I-}

const
  inf = '';
  ouf = '';
  maxn = 101;
  none = maxlongint shr 1;

type integer = longint;

var cost: array[1..maxn, 1..maxn] of integer;
    lev, dis: array[1..maxn] of integer;
    x: array[1..maxn] of boolean;
    s, n, m: integer;

function min(i, j: integer): integer;
begin
  if i < j then min := i else min := j;
end;

procedure prepare;
var i, j, u, p, k: integer;
begin
  read(m, n);
  s := n + 1;
  for i := 1 to s do
    for j := 1 to s do
      cost[i, j] := none;
  for i := 1 to n do begin
    read(p, lev[i], k);
    cost[s, i] := p;
    for j := 1 to k do begin
      read(u, p);
      cost[u, i] := p;
    end;
  end;
end;

function dij(low: integer): integer;
var u, i: integer;
begin
  for i := 1 to n do dis[i] := none; dis[s] := 0;
  for i := 1 to n do x[i] := (lev[i] >= low) and (lev[i] - low <= m);
  u := s;
  while x[1] do begin
    x[u] := false;
    for i := 1 to n do if x[i] then dis[i] := min(dis[i], dis[u] + cost[u, i]);
    u := 0;
    for i := 1 to n do if x[i] and ((u = 0) or (dis[i] < dis[u])) then u := i;
  end;
  dij := dis[1];
end;

procedure main;
var i, ans: integer;
begin
  ans := none;
  for i := 1 to n do ans := min(ans, dij(lev[i]));
  writeln(ans);
end;

begin
  assign(input, inf); assign(output, ouf);
  reset(input); rewrite(output);
  prepare;
  main;
  close(input); close(output);
end.

   Пример решения на С++:

#include "stdio.h"
#include "string.h"
#include "iostream"
#define max 102
#define MAX 999999999
using namespace std;
int lv, n, map[max][max], tmap[max][max], rank[max], trank[max], ok[max], s[max], d[max];
int dj(int x){
    int i, j, w, min;
    memset(s, 0, sizeof(s));
    memset(d, -1, sizeof(d));
    for(i = 1; i <= n + 1; i++){
        if(map[x][i])d[i] = map[x][i];
        if(!ok[rank[i]]){
            s[i] = 1;
            d[i] = MAX;
        }
    }
    while(1){
        w = -1;
        for(i = 1; i <= n + 1; i++){
            if(!s[i] && d[i] >= 0){
                if(w == -1 || d[i] < min){
                    min = d[i];
                    w = i;
                }
            }
        }
        if(w == -1)break;
        s[w] = 1;
        for(i = 1; i <= n + 1; i++){
            if(map[w][i]){
                if(d[i] < 0 || d[i] > d[w] + map[w][i])
                    d[i] = map[w][i] + d[w];
            }
        }
    }
    return d[1];
}
int main(){
    int i, j, u, v, w, res, cost, nlv, t, l, r, xx;
    while(scanf("%d%d", &lv, &n) != -1){
        res = MAX;
        memset(map, 0, sizeof(map));
        memset(tmap, 0, sizeof(tmap));
        for(i = 1; i <= n; i++){
            scanf("%d%d%d", &cost, &nlv, &t);
            tmap[n + 1][i] = map[n + 1][i] = cost;
            rank[i] = trank[i] = nlv;
            for(j = 1; j <= t; j++){
                scanf("%d%d", &u, &cost);
                map[u][i] = tmap[u][i] = cost;
            }
        }
        trank[n + 1] = rank[n + 1] = trank[1] = rank[1];
        for(l = lv, r = 0; l >= 0; l--, r++){
            xx = 0;
            memset(ok, 0, sizeof(ok));
            for(i = l; i > 0; i--){
                if(rank[1] - i >= 0)
                ok[rank[1] - i] = 1;
            }

            ok[rank[1]] = 1;
            for(j = 1; j <= r; j++){
                ok[rank[1] + j] = 1;
            }
            if(res > (w = dj(n + 1)))
                res = w;
        }
        printf("%d\n", res);
    }
    return 0;
}