题目描述
给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环, 边权可能为负数
请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离
如果无法从 1 号点走到 n 号点,输出 impossible
注意:图中可能 存在负权回路
样例
输入样例:
3 3 1
1 2 1
2 3 1
1 3 3
输出样例:
3
Bellman_ford算法
(迭代加深) $O(nm)$
算法流程:
1.扫描所有(x,y,z),若dist[y]>dist[x]+z,则用dist[x]+z更新dist[y]
2.重复上述步骤,直到没有更新操作发生
时间复杂度
迭代加深,双重循环
点数n
x 边数m
即 $O(nm)$
$\color{#32CD32}{Accepted}$ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int n,m,k;
int s[N],e[N],w[N];
int dist[N],last[N];
void bellman_ford()
{
memset(dist,0x3f,sizeof dist);
dist[1]=0;
for(int i=0;i<k;i++)
{
memcpy(last,dist,sizeof dist);
for(int j=0;j<m;j++)
{
int u=s[j],v=e[j];
dist[v]=min(dist[v],last[u]+w[j]);
}
}
}
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);
s[i]=a,e[i]=b,w[i]=c;
}
bellman_ford();
if(dist[n]>100000000)printf("impossible");
else printf("%d",dist[n]);
return 0;
}