Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
981. Schedule
Кратчайшие пути из одной вершиныОлимпиадные задачи на английском языке
| 03/07/2008 | Лето 2008 дорешивание ( 6G) |
| 14/07/2008 | Лето 2008 - 6 (G) |
Ограничения: время – 1s/2s, память – 16MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
There are many tasks which need to be done in order to construct a building. In order to perform these tasks, there should be a reasonable schedule. There might be relations between tasks. The difficulty we meet in creating a schedule is that the schedule has to satisfy all given relations among the given tasks.
Given a set of tasks and their relations, your task is to write a program to check whether it is possible to create a schedule to perform the tasks.
Input
The first line contains two integers `n` and `k` (`1\ ≤\ n\ ≤\ 500`, `0\ ≤\ k\ ≤\ 20000`), where `n` denotes the total number of tasks, and `k` denotes the total number of relations. The next `k` following lines describes `k` relations among the tasks. Let `t_j` be a starting time of the task `j`, `j\ =\ 1,\ 2,\ …,\ n`. Each relation is one of the two forms:
- `x\ y\ v` means task `x` must not start after task `y` starts `v` days, i.e. `t_x\ ≤\ t_y\ +\ v`,
- `x\ y\ -v` means task `x` must not start before task `y` starts `v` days, i.e. `t_x\ ≥\ t_y\ +\ v`,
where `v` is positive integer not greater than `10\ 000`.
Output
Write "YES" if it is possible to construct a schedule to satisfy all the given relations among the given task, "NO" otherwise.
Sample Input 1
2 2 1 2 -2 1 2 1
Sample Output 1
NO
Sample Input 2
2 1 1 2 -1
Sample Output 2
YES
