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 
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 ≤ I ≤ N) para a sala F (1 ≤ F ≤ N) 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 |
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;
}
Input
1 1
1 2 1
2 1 3
Output