给定一个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算法 思想 for k次循环 for i~m次循环 dist[b]=min(dist[b],w[i]+dist[a]);
#include<bits/stdc++.h> using namespace std; const int N=510; int n,m,k; int dist[N],fu[N];//dist 到i的最短距离 fu 辅助数组 //这个算法可以用任何办法存储边 只要可以遍历到每条边 struct kl{ int a,b,c; }as[15000]; //使用结构体储存边 int bellmanford(){ memset(dist,0x3f,sizeof(dist));dist[1]=0;//初始化 for(int i=0;i<k;i++){ memcpy(fu,dist,sizeof(dist));//复制 使每一次循环相当于只向终点n走了一条边 for(int j=0;j<m;j++) dist[as[j].b]=min(dist[as[j].b],fu[as[j].a]+as[j].c);//更新距离 } if(dist[n]>0x3f3f3f3f/2) return -1; return dist[n]; } int main(){ cin>>n>>m>>k; for(int i=0;i<m;i++) cin>>as[i].a>>as[i].b>>as[i].c; int t=bellmanford(); if(t==-1) cout<<"impossible"; else cout<<t; return 0; }总结 算法的复杂度较高O(km); 适用情况可能较少 这道题却必须用这个
