感觉这题怎么做都不会超时，因此写了一个Bellman-Ford，居然过了……程序才50行……

p.s. 一开始没看到双向边，多传了2次……

这题难度不能说有4

太简单了点

以前看不懂题

现在看懂了发现好简单

M写成了N

10分

改了

AC

不敢置信的一次ac...

想通了比较简单 而且可以放心大胆做 怎么做都不会超...

一次AC。。详见jsydtc神牛的题解。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

事实证明，freepascal for NOI 这个版本通常会隐瞒你的错误

不错的题，最短路+dp，不知怎么没人做。

f[i]:=min(f[j-1]+dijstra(j,i)*(i-j+1)+k，dijkstra(1,i)*i)

dijstra（j,i）是从j到i的时间都能走得最短路长度.

我wa了5次，竟然是建图的时候敲成了map[x,y]:=z;

map[y,z]:=z;

我的ac率啊！！！

求详细解答！！！！

DP+SPFA......

用dp + dijkstra

肯定正确

bfs求出所有有意义的航线，然后DP

用F表示前I天的最少费用，那么状态转移就可以通过计算第J天（1

郁闷啊.........

简单DP。

当然状态转移时要用dijkstra算出最短路后再求最优解。

不是什么难题，别想得太难了，状态就一维......