这里采用邻接矩阵实现Bellman Ford算法;可以参考blog;
限于时间,暂时只写下代码,以后有时间补上…
#include<iostream> #include<cstring> #define clr(x) memset(x,0,sizeof(x)) #define maxn 1000+5 using namespace std; const int maxint=1<<(sizeof(int)*8-1)-1; int n,m,k; //点数,边数 int mp[maxn][maxn]; int dis[maxn],path[maxn]; void chushihua() { cin>>n>>m>>k; for(int i=0; i<=n; i++) for(int j=1; j<=n; j++) mp[i][j]=maxint; for(int i=0; i<m; i++) { int v1,v2,w; cin>>v1>>v2>>w; mp[v1][v2]=w; } } //Bellman Ford算法 bool solve(int s,int t) { for(int i=1; i<=n; i++) { dis[i]=mp[s][i]; if(i!=s && dis[i]<maxint) path[i]=s; //当前不是起点并且可以到达,设前驱位起点s else path[i]=-1; } // for(int i=0;i<n;i++) cout<<path[i]<<" \t"<<dis[i]<<endl; for(int i=0; i<k-1; i++) { for(int u=1; u<=n; u++) { if(u==s) continue; for(int v=1; v<=n; v++) { if(mp[v][u]<maxint && dis[u]>dis[v]+mp[v][u]) { dis[u]=dis[v]+mp[v][u]; path[u]=v; } } } // for(int j=1; j<=n; j++) cout<<dis[j]<<" "; cout<<endl; // for(int j=1; j<=n; j++) cout<<path[j]<<" ";cout<<endl; } if(dis[t]>maxint/2) return false; //不可到t else return true; } int main() { chushihua(); if(solve(1,n)) cout<<dis[n]<<endl; else cout<<"impossible"<<endl; return 0; }
以下示例没有通过:
10 20 8
4 2 7
8 7 10
1 3 1
7 6 1
4 5 8
8 7 5
5 7 1
6 10 2
3 1 9
5 4 4
4 7 1
9 9 9
8 1 8
5 4 5
7 6 5
3 7 7
4 9 1
2 1 9
2 9 9
6 1 -2
11
#include<iostream> #include<cstring> #define clr(x) memset(x,0,sizeof(x)) #define maxn 10000+5 using namespace std; const int maxint=1<<(sizeof(int)*8-1)-1; typedef struct Edge { int v1,v2; int w; void show() { cout<<"u="<<v1<<"\tv="<<v2<<"\tw="<<w<<endl; } } Edge; int n,m,k; Edge edges[maxn]; int dis[maxn],path[maxn]; void chushihua() { cin>>n>>m>>k; for(int i=1; i<=m; i++) { int v1,v2,wei; cin>>v1>>v2>>wei; edges[i].v1=v1; edges[i].v2=v2; edges[i].w=wei; } } bool solve(int s,int t) { for(int i=1; i<=n; i++) dis[i]=maxint; dis[s]=0; for(int i=0; i<k; i++) { int tmp[maxn]; for(int j=1; j<=n; j++) tmp[j]=dis[j]; for(int j=1; j<=m; j++) { int v1=edges[j].v1, v2=edges[j].v2, w=edges[j].w; if(dis[v2]>tmp[v1]+w) { // edges[j].show(); dis[v2]=tmp[v1]+w; path[v2]=v1; } } } if(dis[t]>=maxint/2) return false; else return true; } int main() { chushihua(); if(solve(1,n)) cout<<dis[n]<<endl; else cout<<"impossible"<<endl; return 0; }
2021-06-1 更新,感谢观看-