最短路 - BellFord算法

有边数限制，存在负权边

题目描述

给定一个n个点m条边的有向图，图中可能存在重边和自环，边权可能为负数。
请你求出从1号点到n号点的最多经过k条边的最短距离，如果无法从1号点走到n号点，输出impossible.
注意:图中可能 存在负权回路。
输入格式
第一行包含三个整数n，m，k。
接下来m行，每行包含三个整数x，y，z，表示点x和点y之间存在一有向边长为z。
输出格式
输出一个整数，表示从1号点到n号点的最多经过k条边的最短距离。
如果不存在满足条件的路径，则输出“impossible”。
数据范围
1 ≤n,k≤ 500,
1<m< 10000.
任意边长的绝对值不超过10000。

样例输入：

3 3 1
1 2 1
2 3 1
1 3 3

样例输出：

3

// 最短路 - Bellman_Ford算法
// 存在负权边，有边数限制时
// 有负权回路最短路不一定存在
// 单源最短路算法 从 1 号点到其它点的距离#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;const int N=510,M=10010;
int n,m,k;
int dist[N],backup[N];struct Edge
{int a,b,w;
} edges[M] ;int bellman_ford()
{memset(dist,0x3f,sizeof dist);dist[1]=0;//从 1 号点经过不超过 k 条边到 n 号点最短路的距离for(int i=0;i<k;i++){memcpy(backup,dist,sizeof dist);for(int j=0;j<m;j++){int a=edges[j].a,b=edges[j].b,w=edges[j].w;dist[b]=min(dist[b],backup[a]+w);}}if(dist[n]>0x3f3f3f3f/2) return -1;return dist[n];
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m>>k;for(int i=0;i<m;i++){int a,b,w;cin>>a>>b>>w;edges[i]={a,b,w};}int t=bellman_ford();if(t==-1) puts("impossable");else cout<<t<<endl;return 0;
}