题目描述

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

输入样例：
3 3 1
1 2 1
2 3 1
1 3 3
输出样例：
3

样例

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 510, M = 100010;
int n,m,k;

//定义dist[]表示从源点到点 n 的距离
//定义back[]存储dist[]的备份数据
int dist[N],back[N];

//定义结构体来存储点和边
struct Edge
{
    //由 a 指向 b 权重为 w 的边
    int a,b,w;
}edge[M];

string bellman_ford()
{
    //初始化dist[]数组
    //以编号为1的点作为源点,所以结点 1 跟源点的距离为 0
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;
    //遍历 k 次
    for(int i = 0; i < k; i++)
    {
        //在每次循环前对dist[]进行备份
        //避免串联的情况发生
        memcpy(back,dist,sizeof dist);
        //遍历每条边
        for(int j = 0; j < m; j++)
        {
            int a = edge[j].a;
            int b = edge[j].b;
            int w = edge[j].w;
            //确保每一次松弛中
            //只会更新与该结点相邻的点的距离
            //不会和下一次循环抢活干
            //其实是因为外面限制了不超过 k 条边
            //所以下以条边的松弛会不会发生还是未知的
            dist[b] = min(dist[b],back[a] + w);
        }
    }
    //例如 1--> 2 --> 3      4 --> 5( 4 到 5 的边长为 -10)
    // 1 结点没法到 5 结点 但是当在对 4 到 5 这条边进行松弛时
    //dist[5] 会小于 0x3f3f3f3f 所以只要dist[] 大于和 0x3f3f3f3f 同级别的数
    //就认为这俩个点是不连通的

    //数据加强了,可能会出现源点到某个点的最短路径为 -1 
    //所以不能再判断不存在路径后就返回 -1 了
    //这个无所谓,改一下不存在的标志罢了
    if(dist[n] >= 0x3f3f3f3f / 2) return "no";
    else return "yes";
}

int main()
{
    cin>>n>>m>>k;
    for(int i = 0; i < m; i++)
    {
        int x , y , z;
        cin>>x>>y>>z;
        edge[i] = {x,y,z};
    }

    string t = bellman_ford();
    if(t == "no") cout<<"impossible"<<endl;
    else cout<<dist[n]<<endl;

    return 0;
}