百度一面
并未手撕该题,而是考察思路口述
最难的理解的就是第二个循环,y总在课上没怎么讲。
我的理解是第二个循环每次都更新一遍整个dist[N]数组,更新n-1
次时,图中所有点到起始点 (随便设)都已经更新好了,我们想求任意起始点->终结点
的最短路径都ok,只要取出dist[n]
就行了。不止是把t->(t的下一个节点)的最短路径加上,而是要全图刷新
当然第二个循环每次更新dist时,有意义的值只有和当前节点t
直连的节点的dist[j]
,根据dist[j] = min(dist[j], dist[t] + g[t][j]);
不直连的点就是两个无穷取最小值还是无穷
dist[t]:走到的当前节点t到起始点
的最短路径
dist[j]:加一个for循环
,就是整个图的所有节点到起始节点的最短路径
整个Dijkstra算法就是一个探索战争迷雾的开图的过程,每发现了一个新的资源点(节点),刷新一下地图(全图),刷新同时计算出其到主基地的最短路径,全图都开完了也就刷新了出了所有资源点到主基地的最短路径
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 510;
int n, m;
int g[N][N];
int dist[N];
bool st[N];
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
// 走到n-1个点停下
for (int i = 0; i < n - 1; i ++ )
{
int t = -1;
// 找到一个不在集合st内,且距离最短的节点t,走到t上
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
st[t] = true; // 第t个点算过最短路径了
// 起始状态,算出所有直连节点1的节点j们的dist[j]并取最短点,
// 不直连的算完还是无穷
// 更新状态:沿着上一次循环算出的最短节点路径, 更新其为t,在第一个循环实现了
// 计算t节点直连的所有节点j的dist[j]并取最短点
// 重复这两个循环,1、找最短点t走过去 2、更新这个点t所有的最短路径dist[t]
// 第二个循环每次更新一遍整个dist[N]数组,最后想知道到那个点最短,取dist[n]就可以了
// 当整个图走了n-1个点时,每个点的最短路径就更新出来了
for (int j = 1; j <= n; j ++ )
{
dist[j] = min(dist[j], dist[t] + g[t][j]);
// cout << dist[j] << ' ';
}
// cout << endl << "t " << dist[t] << endl;
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main()
{
scanf("%d%d", &n, &m);
memset(g, 0x3f, sizeof g);
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a][b] = min(g[a][b], c);
}
printf("%d\n", dijkstra());
return 0;
}