Участник:ZhenyaStrelkova/GORELIAN

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/GORELIAN/

#include<iostream>
 
using namespace std;
 
const int infinity = 1000000;
const int max_value = 500;
const int rels = 2520;
 
int main() {
    int N, M, val, pos;
    char dir;
    int field[max_value][max_value], visited[max_value], path[max_value];
    cin >> N >> M;
    while ((N + M) != 0) {
 
        for (int i = 0; i < max_value; i++) {
            path[i] = infinity;
            visited[i] = 0;
            for (int j = 0; j < max_value; j++)
                field[i][j] = infinity;
        }
        pos = 0;
 
        for (int i = 0; i < 2 * N + 1; i++) {
            if (i % 2 == 0) {
                for (int j = 0; j < M; j++) {
                    cin >> val >> dir;
                    val = (val != 0) ? rels / val : infinity;
                    if (dir == '*') {
                        field[pos][pos + 1] = val;
                        field[pos + 1][pos] = val;
                    }
                    else if (dir == '>')
                        field[pos][pos + 1] = val;
                    else
                        field[pos + 1][pos] = val;
                    pos++;
                }
                pos++;
            } else {
                for (int j = 0; j <= M; j++) {
                    cin >> val >> dir;
                    val = (val != 0) ? rels / val : infinity;
                    if (dir == '*') {
                        field[pos][pos - M - 1] = val;
                        field[pos - M - 1][pos] = val;
                    }
                    else if (dir == 'v')
                        field[pos - M - 1][pos] = val;
                    else
                        field[pos][pos - M - 1] = val;
                    pos++;
                }
                pos = pos - M - 1;
            }
        }
 
        N = (N + 1) * (M + 1);
        int min, store = 0, src = 0;
        for (int i = 0; i < N; i++) {
            visited[src] = 1;
            min = -1;
            for (int j = 0; j < N; j++) {
                if (visited[j])
                    continue;
                if (min == -1)
                    min = j;
                if (store + field[src][j] < path[j])
                    path[j] = store + field[src][j];
                if (path[j] < path[min])
                    min = j;
            }
            src = min;
            store = path[min];
        }
 
        if (path[N - 1] == infinity)
            cout << "Holiday\n";
        else
            cout << path[N - 1] << " blips\n";
 
        cin >> N >> M;
    }
 
    return 0;
}