- 解決單源最短路問題
- 限制更新次數(shù)的最短路問題窍侧，一定是用bellman-ford
- 可以求是否含有負(fù)環(huán)（第n次循環(huán)窗声，如果仍然有更新承绸，則說明含有負(fù)環(huán)）
時(shí)間復(fù)雜度：o(nm)
n個(gè)點(diǎn)兜蠕，m條邊
787. K 站中轉(zhuǎn)內(nèi)最便宜的航班
const int M = 5010;
const int N = 105;
class Solution {
public:
struct edge
{
int u;
int v;
int w;
}edges[M];
int dist[N];
int back[N];
int bellman_ford(int k,int edgesCounts,int src,int dst)
{
memset(dist,0x3f,sizeof dist);
dist[src] = 0;
for (int i = 0; i < k; i++)
{
memcpy(back,dist,sizeof dist);
for (int j = 0; j < edgesCounts; j++)
{
dist[edges[j].v] = min(dist[edges[j].v], back[edges[j].u] + edges[j].w);
}
}
return dist[dst] == 0x3f3f3f3f ? -1 : dist[dst];
}
int findCheapestPrice(int n, vector<vector<int>>& nums, int src, int dst, int K) {
for (int i = 0; i < nums.size(); i++)
{
edges[i].u = nums[i][0];
edges[i].v = nums[i][1];
edges[i].w = nums[i][2];
}
return bellman_ford(K+1,nums.size(),src,dst);
}
};
