题目描述

给定一个 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

算法1

#include<iostream>
#include<cstring>
using namespace std;
const int N=510,M=10010;
int dist[N],backup[N];
int n,m,k;
struct e
{
    int a,b,c;
}edges[M];
int bellman_ford()
{
    //初始化：
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;

    for(int i=0;i<k;i++)    //不超过k条边，就迭代k次
    {
        memcpy(backup,dist,sizeof dist);    //每次都使用上一次的dist数组（backup），防止发生串联
        for(int j=0;j<m;j++)    //迭代所有边
        {
            int a=edges[j].a,b=edges[j].b,c=edges[j].c;
            dist[b]=min(dist[b],backup[a]+c);
        }
    }
    if(dist[n]>0x3f3f3f3f/2)
        return -1;
    else
        return dist[n];
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    int x,y,z;
    for(int i=0;i<m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        edges[i]={x,y,z};
    }
    int t=bellman_ford();
    if(t==-1)
        puts("impossible");
    else
        cout<<t<<endl;
    return 0;
}

算法2

package searchGraph;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

/**
 * AcWing 853. 最短路之有边数限制的最短路  bellman_ford算法(处理负权回路+边数限制)
 * https://www.acwing.com/problem/content/855/
 * Created by Yolanda on 2021/7/18 10:14
 */

public class bellman_ford {
    static int N=510,M=10010;
    static int mmax=0x3f3f3f3f;
    static int[] dist=new int[N];
    static int[] backup=new int[N];
    static int n,m,k,x,y,z;
    public static class edge
    {
        private int x;
        private int y;
        private int w;
        public edge(int x, int y, int w) {
            this.x = x;
            this.y = y;
            this.w = w;
        }
    }
    static edge[] e=new edge[M];
    static int bellmanford()
    {
        Arrays.fill(dist, mmax);
//        for (int i = 0; i < N; i++) {
//            dist[i] = mmax;
//        }
        dist[1] = 0;
        while(k-->0)
        {
            //每次对dist数组进行一次备份
            //备份原因：每次只会从上一轮的结果里面去改动，不会被本轮改动的值所影响
            backup = Arrays.copyOf(dist, N);
//            for (int j = 0; j < N; j++)
//                backup[i] = dist[i];

            for (int j = 1; j <=m; j++)
            {
                int a = e[j].x, b = e[j].y, w = e[j].w;
                dist[b] = Math.min(dist[b], backup[a] + w);
            }
        }
        if(dist[n]>mmax/2)
            return -1;
        else
            return dist[n];
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String[] a=br.readLine().split(" ");
        n= Integer.parseInt(a[0]);
        m= Integer.parseInt(a[1]);
        k= Integer.parseInt(a[2]);
        for (int i = 1; i <= m; i++)
        {
            String[] b=br.readLine().split(" ");
            x= Integer.parseInt(b[0]);
            y= Integer.parseInt(b[1]);
            z= Integer.parseInt(b[2]);
            e[i]=new edge(x,y,z);    //勿忘此句！！！
//            e[i].x=x;e[i].y=y;e[i].w=z;
        }
        int t=bellmanford();
        if(t==-1)
            System.out.println("impossible");
        else
            System.out.println(t);
    }
}