whust 2016 warm up E ||codeforces 689 B. Mike and Shortcuts (spfa)

cf689B题目链接

题意:n点。。点i到点j的代价是|i-j|..给出n条近路。。。a[i]表示点i到a[i]的代价为1(注意近路不一定就近)

思路:一开始建边卡了一下。。。实际上只要连相邻的就好了。。。然后边表只开了2*N蠢哭。。。实际上应该3*M…因为连相邻的边是双向的。。。再[……]

Read more

hdu 3873 Invade the Mars (有限制条件的最短路。。)

hdu3873题目链接

题意:n个点的图。。。每个点可能被若干其他点保护。。。被保护的意思是。。。如果想访问某个点。。那么必须先访问保护该点的所有点。。。问从点1到点n的最小代价。。

思路:。。一开始写了spfa。。。然后一脸懵逼。。。因为我第一次访问某个点的时候无法保证距离是最短的。。[……]

Read more