求“最小代价”问题：对于一个有向图，每个点都有一个值wi，wi > 0，原点s到该点的代价为s到该点的wi之和。设计算法，求s到每个点的最小代价，写伪代码，分析时间复杂度，证明算法正确性

这是一个经典的单源最短路问题，可以使用Dijkstra算法或者Bellman-Ford算法解决。这里给出Bellman-Ford算法的伪代码：

procedure Bellman-Ford(s)
    for each vertex v in vertices:
        dist[v] := infinity
    dist[s] := 0
    for i from 1 to |V|-1:
        for each edge (u, v) with weight w in edges:
            if dist[u] + w < dist[v]:
                dist[v] := dist[u] + w
    return dist

其中，dist[v]表示从原点s到顶点v的最短路径长度，infinity表示一个很大的数，|V|表示图中顶点的个数。算法的时间复杂度为O(|V||E|)，其中|E|表示图中边的个数。

正确性证明：

我们考虑算法的每一轮松弛操作都会使得从原点s到某个顶点v的最短路径长度最多减少一次，因为每次松弛操作都会将当前路径上的一个顶点的最短路径长度更新为更小的值。所以，当算法结束时，从原点s到每个顶点v的最短路径长度就已经被计算出来了。

同时，Bellman-Ford算法还能够检测负权回路，即如果经过一条权值之和为负数的回路，最短路径长度将没有意义。算法在每次迭代时，检查是否存在这样的回路，并在发现回路后停止执行，返回一个错误状态。

因此，Bellman-Ford算法既可以求解最短路径问题，又能够检测负权回路，保证了算法的正确性。