Algorithm


Problem Name: 2 AD-HOC - beecrowd | 2308

Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2308

Museu

 

Por OBI - Olimpíada Brasileira de Informática 2006 BR Brazil

Timelimit: 1

Desde que o arquiteto Frank Gehry projetou o Museu Guggenheim de Bilbao, os museus têm sido construídos com formas cada vez mais complexas, fugindo de padrões pré-estabelecidos e de simetrias. Um típico museu moderno é composto por um conjuto de salas ligadas por corredores e escadas, sem preocupação com a prédefinição de caminhos a serem seguidos pelas pessoas.

Henriqueta é uma professora do ensino fundamental que deseja visitar o museu da Ordem Brasileira de Medicina (OBM) para mostrar aos seus alunos de ciências como o corpo humano funciona e como as cirurgias eram feitas nos séculos XIX e XX. Henriqueta quer planejar uma visita pelas salas do museu, obedecento as seguintes restrições:

  • a visita deve começar e terminar em uma mesma sala;
  • exceto a sala de partida, nenhuma sala do museu pode ser visitada mais de uma vez;
  • a visita deve incluir pelo menos duas salas;
  • os corredores são unidirecionais, ou seja, as pessoas podem caminhar, em um corredor, apenas em uma direção.
  • a visita deve tomar o menor tempo possível.

Um estudo preliminar, realizado pelo próprio museu, indica o tempo médio que cada visitante fica em uma sala e quanto tempo leva-se para atravessar um corredor ou uma escada. Henriqueta quer a sua ajuda para calcular o tempo total da menor visita que ela pode efetuar, obedecendo as restrições dadas.

Escreva um programa que, dados um conjunto de salas, um conjunto de corredores e escadas que ligam essas salas e o tempo necessário para percorrer cada sala e cada corredor, determine qual é o menor tempo possível para uma visita. Note que o tempo de visita da sala onde a visita se inicia deve ser contado apenas uma vez.

 

Entrada

 

A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado). A primeira linha da entrada contém dois inteiros S e C, que indicam, respectivamente, o número de salas (1 ≤ S ≤ 1000) e o número de corredores e escadas (1 ≤ C ≤ 1000). As salas são numeradas de 1 a S. A segunda linha contém S inteiros representando o tempo gasto para percorrer cada sala. Cada uma das C linhas seguintes descreve um corredor ou escada. A descrição ´e composta por três inteiros, I, F e T , indicando que o corredor somente pode ser percorrido da sala I (1 ≤ IN) para a sala F (1 ≤ FN) no tempo T (1 ≤ T ≤ 1000). O tempo total máximo é sempre menor ou igual a 1000000.

 

Saída

 

Seu programa deve imprimir, na saída padrão, uma única linha contendo o tempo gasto na visita de menor duração que Henriqueta pode realizar no museu. Existe pelo menos uma visita que atende as restrições impostas.

 

 

 

Exemplos de Entrada Exemplos de Saída

2 2
1 1
1 2 1
2 1 3

6

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming


#include <algorithm>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
typedef pair < int, int> ii;
typedef vector<ii> vii;
#define MAXN 1001
#define LIMIT 1000001
#define MP make_pair
vii grafo[MAXN];
int matriz[MAXN][MAXN], tempo[MAXN], resposta = LIMIT, visitado[MAXN][MAXN];
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i  < = n; i++) {
        scanf("%d", &tempo[i]);
        for (int j = 1; j  < = n; j++) matriz[i][j] = LIMIT;
    }
    for (int i = 1; i  < = m; i++) {
        int u, v, duracao;
        scanf("%d %d %d", &u, &v, &duracao);
        grafo[u].push_back(MP(tempo[v] + duracao, v));
    }
    for (int i = 1; i  < = n; i++) {
        priority_queue > heap;
        for (int j = 0; j  <  (int)grafo[i].size(); j++) heap.push(grafo[i][j]);
        while (!heap.empty()) {
            ii davez = heap.top();
            heap.pop();
            if (visitado[i][davez.second]) continue;
            visitado[i][davez.second] = 1;
            matriz[i][davez.second] = davez.first;
            for (int j = 0; j  <  (int)grafo[davez.second].size(); j++)
                heap.push(MP(davez.first + grafo[davez.second][j].first,
                             grafo[davez.second][j].second));
        }
    }
    for (int i = 1; i  < = n; i++)
        for (int j = 1; j  < = n; j++)
            resposta = min(resposta, matriz[i][j] + matriz[j][i]);
    printf("%d\n", resposta);
    return 0;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
2 2
1 1
1 2 1
2 1 3

Output

x
+
cmd
6
Advertisements

Demonstration


Previous
#2305 Beecrowd Online Judge Solution 2305 Colheita de Caju Solution in C, C++, Java, Js and Python
Next
#2309 Beecrowd Online Judge Solution 2309 Truco Solution in C, C++, Java, Js and Python