题目分析
这道题目直接运用Bellman-Ford算法进行求解
注意点
1、使用Bellman-Ford算法时要注意设置一个lastdix[N]
数组用来存储上一轮数据,确保第i次循环只更新第i层结点
memcpy(lastdis,dis,sizeof dis); //保留上一次迭代的dist的副本,防止跨层数更新
2、输入数据中两点之间可能会存在多条路径,注意只记录下最短的那一条就可以
for(int i=0;i<m;i++){
int x,y,z;
cin>>x>>y>>z;
if(G[x][y]>z) G[x][y]=z;
}
算法
#include<bits/stdc++.h>
using namespace std;
const int N=510;
const int INF=1000000;
int dis[N];
int lastdis[N];
int G[N][N];
int n,m,k;
void BF(){
fill(dis,dis+N,INF);
dis[1]=0;
//这里其实使用了树的思想 以源点为根节点建立一棵最短路径树,依次找到各层上的点
for(int i=0;i<k;i++){ //保证第i次循环只用来更新第i层结点数据
memcpy(lastdis,dis,sizeof dis); //保留上一次迭代的dist的副本,防止跨层数更新
for(int u=1;u<=n;u++)
for(int v=1;v<=n;v++){
if(lastdis[u]+G[u][v]<dis[v]&&G[u][v]!=INF&&lastdis[u]!=INF){
dis[v]=lastdis[u]+G[u][v];
}
}
}
}
int main(){
cin>>n>>m>>k;
fill(G[0],G[0]+N*N,INF);
for(int i=0;i<m;i++){
int x,y,z;
cin>>x>>y>>z;
if(G[x][y]>z) G[x][y]=z;
}
BF();
if(dis[n]!=INF) cout<<dis[n];
else cout<<"impossible";
return 0;
}