AcWing853.有边数限制的最短路(Bellman_ford算法)

本文主要是介绍AcWing853.有边数限制的最短路(Bellman_ford算法)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【题目链接】853. 有边数限制的最短路 - AcWing题库

【题目描述】

输入样例：

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

输出样例：

3

【代码及详细注释】

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
struct node{int a,b,w;//表示每条边的起点终点和边长	 
}e[N];
int n,m,k,dist[N],mp[N];//用于备份的数组
void bellman_ford()
{memset(dist,0x3f,sizeof dist);dist[1]=0;for(int i=0;i<k;i++)//最多走k次{memcpy(mp,dist,sizeof dist);for(int j=1;j<=m;j++){int a=e[j].a,b=e[j].b,w=e[j].w;dist[b]=min(dist[b],mp[a]+w);//使用备份的距离去更新 }} if(dist[n]>0x3f3f3f3f/2) cout<<-1;else cout<<dist[n];return;
}
int main()
{cin>>n>>m>>k;for(int i=1;i<=m;i++)cin>>e[i].a>>e[i].b>>e[i].w;bellman_ford();return 0;	
}

 

这篇关于AcWing853.有边数限制的最短路(Bellman_ford算法)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---