We say that an edge (x,y) in a directed simple graph G is a shortcut edge when there is a path in G from x to y which length is at least 2. Let the cost of a shortcut edge(x,y) be the length of the longest path from x to y in G.

Given a directed acyclic graph G determine the sum of costs of all its shortcut edges.

Řešení pomocí Floyd-Warshalla je neučinné. Projde na 2/12.

Postup na 11/12: Prochazel jsem graf pro kazdej vrchol pomoci DFS. S tim, ze jsem od spoda propagoval cenu vrcholu - ty nejnizsi byli koncovy a urcite nemeli zadne sousedy, ty nad tim meli za sousedy maximalne ty bez zadneho, atd. Uz projity vrcholy jsem uzaviral a pouzival uz spocitanou cenu. Na konec se pro vsechny sousedy zkontroluje jejich nejvetsi vzdelanost a to jsou zkratky.

Odkaz na zdrojaky: pal.zip