题目

描述

给定一个n个点m条边的有向图，图中可能存在重边和自环，边权可能为负数。

请你求出从1号点到n号点的最多经过k条边的最短距离，如果无法从1号点走到n号点，输出impossible。

注意：图中可能存在负权回路。

输入

第一行包含三个整数n、m、k。

接下来m行，每行包含三个整数x、y、z，表示存在一条从点x到点y的有向边，边长为z。

点的编号为1∼n。

输出

输出一个整数，表示从1号点到n号点的最多经过k条边的最短距离。

如果不存在满足条件的路径，则输出impossible。

数据范围

1≤n,k≤500

1≤m≤10000

1≤x,y≤n

任意边长的绝对值不超过 10000。

bellman_ford算法

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;

const int N=505,M=10010;
#define Inf 0x3f3f3f3f

struct Edge
{
    int x,y,z;
}edges[M];

int n,m,k;
int dist[N];
int last[N];

void bellman_ford()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;

    for(int i=0;i<k;i++)
    {
        memcpy(last,dist,sizeof dist);//备份
        for(int j=0;j<m;j++)
        {//松弛操作
            auto e=edges[j];
            dist[e.y]=min(dist[e.y],last[e.x]+e.z);
        }
    }
}

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        edges[i]={x,y,z};
    }
    bellman_ford();
    if(dist[n]>Inf/2)puts("impossible");
    else printf("%d\n",dist[n]);
    return 0;
}

备份的原因是题目限定最多经过k条边，如果不备份而使用dist[e.x]+e.z，则当图中有负边、负环时可能单点被更新多次，则最后得到的结果确实是走了k+条边得到的

算法介绍

bellman_ford与SPFA