文教警備では9時から17時までの警備の仕事を請け負った．警備に就くのは常時一人いれば十分である（複数人いても問題はない）．現在，契約社員の中で仕事が無い人材をリストアップしたところ以下のようになった．
表：現在勤務可能な契約社員の勤務可能時間と雇用コスト
| Aさん | Bさん | Cさん | Dさん | Eさん | Fさん | Gさん | Hさん | |
| 働く時間帯 | 9-12 | 9-11 | 11-13 | 12-15 | 12-17 | 14-17 | 13-16 | 16-17 |
| コスト（千円） | 31 | 14 | 16 | 22 | 38 | 20 | 26 | 9 |
契約の都合上，各契約社員の働く時間を延長したり短縮したりすることはできない．誰に働いてもらえばもっともコストを押さえることができるか．人員の配置計画を提案せよ．
ヒント：うまくネットワークで表現できれば，最短路問題に帰着できます．