Submit | All submissions | Best solutions | Back to list |
ZSHP - Кратчайший путь |
Дан набор городов. Каждая дорога соединяющая города имеет стоимость передвижения (целое число больше 0). НЕобходимо найти путь наименьшей стоимости между любыми двумя городами. Стоимость любого пути (которая равна сумме стоимостей всех дорог состовляющих путь) не превышает 200000. Имена городов это строки содержащие символы 'a'...'z' и не превышающие по длине 10.
Входные данные
s [число тестов <= 10] n [число городов <= 10000] NAME [имя города] p [число соседних городов NAME] nr cost [nr - индекс города соединенного с NAME (индекс первого города - 1)] [cost - стоимость передвижения] r [число путей которые необходимо найти<= 100] NAME1 NAME2 [NAME1 - начало пути, NAME2 - место назначения] [пустая строчка разделяющая тесты]
Выходные данные
cost [минимальная стоимость проезда из города NAME1 до города NAME2 (по одной на каждой строчке)]
Пример
Входные данные: 1 4 zelenograd 2 2 1 3 3 himki 3 1 1 3 1 4 4 piter 3 1 3 2 1 4 1 moscow 2 2 4 3 1 2 zelenograd moscow himki moscow Выходные данные: 3 2
Added by: | Roman Sol |
Date: | 2004-05-10 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM32-GCC ASM64 MAWK BC C-CLANG NCSHARP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM NODEJS OBJC OBJC-CLANG OCT PERL6 PICO PROLOG PYPY PYPY3 R RACKET RUST CHICKEN SED SQLITE SWIFT UNLAMBDA VB.NET |
Resource: | DASM Programming League 2003 (problemset 11) |