743. 网络延迟时间

思路

等价于长度最大为 $k + 1$ 的最短路，bellman-ford很明显。

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int inf = 0x3f3f3f3f;

class Solution {
public:
    vector<int> dist, backup;
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        dist.resize(n, inf);
        dist[src] = 0;
        for(int i = 0; i < k + 1; i++){
            backup = dist;
            for(auto edge : flights){
                int a = edge[0], b = edge[1], c = edge[2];
                dist[b] = min(dist[b], backup[a] + c);
            }
        }
        return dist[dst] == inf ? - 1: dist[dst];
    }
};