题目描述
之前自己试着去用邻接表写这个代码,但写了仨小时,心理还是没底.只要存到所有边就可以了.
盘一下算法的思路:
1.初始化
2.进行迭代(题目中是操作少于k次,那就是最多遍历k条边:while(k–);我目前还不是很清楚为什么要迭代,视频三刷了,还是没找到答案~或许就跟知道1+1=2,但不会证明有点类似吧!)
3.备份数组;就样例来讲,<1,2,1>,<2,3,1>;因为操作不大于k次操作,这里k是1,所以这里只要操作了1次就得重开,也就是备份;如果不备份的话,2->3的距离就不是1了,而是使用了第一次更新的数,那么第二次的数也得被迫更新,变成2了!(1 + 1 = 2),然后进行最短路迭代.
C++ 代码
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 510 , M = 10010;
struct Edge
{
int a,b,c;
}edges[M];
int n,m,k;
int dist[N];
int last[N];//因为会产生"串联",所以创建这个数组;我理解的就是一个几个相互独立的操作之间不再独立了.
void bellman_ford()
{
memset(dist,0x3f,sizeof dist);
dist[1] = 0;
while(k--)
{
memcpy(last,dist,sizeof dist);
//从1开始到n,遍历所有边:m;
for(int i = 0 ; i < m ;i ++)
{
auto e = edges[i];
if(dist[e.b] > last[e.a] + e.c) dist[e.b] = last[e.a] + e.c;
}
}
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i = 0 ; i < m ; i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
edges[i] = {a,b,c};
}
bellman_ford();
if(dist[n] > 0x3f3f3f3f / 2) puts("impossible");
else printf("%d\n",dist[n]);
return 0;
}