URAL 1210. Kind Spirits

Author: 2015-09-14

Uncategorized

, ,

1. 题目

http://acm.timus.ru/problem.aspx?space=1&num=1210

1210. Kind Spirits

Time limit: 1.0 second
Memory limit: 64 MB
Ivanushka the Fool lives at the planet of 0-level. It’s very unpleasant to live there. An awful climate, 80 hours working week, ugly girls… He, as well as every inhabitant of his planet, dreams to get to a planet of N-th level. To the paradise.
At each of the i-th level planets there are several hyperspace transfers to some of the (i+1)-st level planets (but there are no reverse ways). Every transfer is guarded by a spirit. The spirits are usually evil: they demand many galactic bank-notes for each transfer. You know, everyone wants to go to a higher level planet. And one has to pay for the pleasure. More than Ivanushka can even imagine. However, extraordinary situations like a lack of a labor-force at one of the higher level planets sometimes happen, and then the spirits – the guards of the transfers — become kind. Sometimes they give galactic bank-notes themselves if only someone goes to their planets.
In order to embody his dream of heavenly planet Ivanushka has done two things. First of all, he has borrowed a complete map of the Universe. It’s written on the map how much the spirits demand or give for a transfer from this or that planet to another one of the next higher level. Secondly, he has hired a staff of young talanted programmers in order that they will help him to draw the way on the map from his planet to the one of Nth level so that he would spend for the spirits as little money or even earn as much as it is possible.

Input

The first line contains an integer N (0 < N < 30) — an amount of levels of the planets on Ivanushka’s map. Then follow Nblocks of information that describe interlevel transfers. More precisely, the ith informative block describes the scheme of transfers from (i−1)-st level planets to the ones of ith level. Those blocks are separated with a line that contains the only symbol “*”. Planets of each level are numbered with sequential positive integers starting from 1. Each level contains not more than 30 planets. There is the only planet of 0-level: the one that Ivanushka lives at. The first line of a block contains a number Ki — an amount of planets of the ith level. THen follow Ki lines — one for each planet of the ith level. Every line consists of numbers of planets separated with a space of the previous (i−1)st level that one can get from them to the current planet, and the corresponding fees. A fee for each transfer is an integer number from −32768 to 32767; a negative fee means that the kind spirit is ready to pay for such a transfer. Each description line is ended by zero.

Output

should contain the only number — the minimal fee that Ivanushka might pay for a transfer to some planet of the Nth level. The answer may be negative: it means that Ivanushka will not only get to a heavenly planet, but will earn some galactic bank-notes. It’s known that there exists if only one way from Ivanushka’s planet to the one of Nth level.
Problem illustration

Sample

input output 
3
2
1 15 0
1 5 0
*
3
1 -5 2 10 0
1 3 0
2 40 0
*
2
1 1 2 5 3 -5 0
2 -19 3 -20 0

-1
Problem Author: Leonid Volkov
Problem Source: USU Open Collegiate Programming Contest October’2002 Junior Session

2. 思路

给出一个分层结构的星图，共有N层，每一层包含若干星球。在相邻两层中，从下层的某一星球移动到上层的某一星球，可能要缴纳过路费，也可能获得补助。现要从最底层的唯一一个星球，到达最顶层的任意一个星球，求最少路费。最少路费可能为负值，表示该路径有收益。

动态规划。为了方便说明，下面使用“星球(i, j)”表示第i层第j个星球。使用cost[i][j]表示从起点（最底层的唯一一个星球）到达星球(i, j)的最少花费，则有：

cost[i][j] = min(cost[i-1][k] + fee[i-1, k][i, j])

k为第i-1层中，与星球(i, j)相连的各个星球；fee[i – 1, k][i, j]为从星球(i – 1, j)到达星球(i, j)的花费。最后求得到达最顶层各个星球路费的最小值即为答案，即min(cost[N][i])。

3. 代码

代码中，map[i][j] 代表星球(i, j)，是一个Fee的链表，包含了第i-1层中，所有能够到达星球(i, j)的星球编号from 和费用cost 。

#include <cstdio>

const int MAX_LEVEL = 31;
const int MAX_PLANET_PER_LEVEL = 31;
const int MAX_COST = 2147483647;

typedef int Cost[MAX_LEVEL][MAX_PLANET_PER_LEVEL];
typedef struct FeeRecord{
    int from, cost;
    struct FeeRecord *next;
} Fee;
typedef Fee *Map[MAX_LEVEL][MAX_PLANET_PER_LEVEL];

void solveE6b_KindSpirits();
void inputMap(Map map, int levelNum, int planetNum[]);

int main() {
    solveE6b_KindSpirits();
    return 0;
}

Map map;
int cost[MAX_LEVEL][MAX_PLANET_PER_LEVEL];
int planetNum[MAX_LEVEL];
void solveE6b_KindSpirits() {
    int n;
    scanf("%d", &n);
    inputMap(map, n, planetNum);
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j < MAX_PLANET_PER_LEVEL; ++j) {
            cost[i][j] = MAX_COST;
        }
    }
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= planetNum[i]; ++j) {
            Fee *f = map[i][j];
            
            int min = MAX_COST;
            while (f) {
                if (cost[i - 1][f->from] != MAX_COST) {
                    int curr = cost[i - 1][f->from] + f->cost;
                    min = min < curr ? min : curr;
                }
                f = f->next;
            }
            
            cost[i][j] = min;
        }
    }
    
    int result = cost[n][1];
    for (int i = 2; i <= planetNum[n]; ++i)
    result = result < cost[n][i] ? result : cost[n][i];
    
    printf("%d\n", result);
}

void inputMap(Map map, int levelNum, int planetNum[]) {
    for (int i = 1; i <= levelNum; ++i) {
        int num;
        scanf("%d", &num);
        planetNum[i] = num;
        
        for (int j = 1; j <= num; ++j) {
            int from, cost;
            scanf("%d", &from);
            while (from != 0) {
                scanf("%d", &cost);
                
                Fee *f = new Fee();
                f->from = from;
                f->cost = cost;
                f->next = map[i][j];
                map[i][j] = f;
                
                scanf("%d", &from);
            }
        }
        if (i != levelNum) {
            char c;
            scanf("%c", &c);
            while (c != '*')
            scanf("%c", &c);
        }
    }
}