给定一个n个点m条边的有向图,图中可能存在重边和自环, 边权可能为负数。
请你求出从1号点到n号点的最多经过k条边的最短距离,如果无法从1号点走到n号点,输出impossible。
注意:图中可能 存在负权回路 。
输入格式
第一行包含三个整数n,m,k。
接下来m行,每行包含三个整数x,y,z,表示存在一条从点x到点y的有向边,边长为z。
输出格式
输出一个整数,表示从1号点到n号点的最多经过k条边的最短距离。
如果不存在满足条件的路径,则输出“impossible”。
AC代码:
#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
#include <algorithm>
//#define int long long
using namespace std;
typedef pair<int,int>PII;
const int maxn=1e6+5;
struct node {
int u,v,w;
} e[maxn];
int n,m,k,backup[maxn],dis[maxn];
int bellman_ford() {
memset(dis,0x3f3f3f3f,sizeof(dis));
dis[1]=0;
for(int i=1; i<=k; i++) { //bellman_ford算法每迭代一次即相当于更新一条边,即题目所谓的边数限制
memcpy(backup,dis,sizeof(dis));//迭代必须从上一层状态进行迭代,否者会错误更新
for(int j=1; j<=m; j++) {
int a=e[j].u,b=e[j].v,c=e[j].w;
dis[b]=min(dis[b],backup[a]+c);
}
}
if(dis[n]>0x3f3f3f3f/2)return -1;
else return dis[n];
}
int main() {
cin>>n>>m>>k;
for(int i=1; i<=m; i++) {
cin>>e[i].u>>e[i].v>>e[i].w;
}
int t=bellman_ford();
if(t==-1)cout<<"impossible"<<endl;
else cout<<t<<endl;
}