题目链接:https://www.acwing.com/problem/content/855/
时/空限制：1s / 64MB

题目描述

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

解题思路

题意:求在经过的边数不超过k个情况下，求1~n的最短距离。
思路:利用Bellman_Ford算法的松弛原理很容易求解，使用dis_数组的目的是为了防止松弛的次数大于k。

Accepted Code:

/* 
 * @Author: lzyws739307453 
 * @Language: C++ 
 */
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 505;
const int MAXM = 1e4 + 5;
const int inf = 0x3f3f3f3f;
int dis[MAXN], dis_[MAXN];
struct edge {
    int u, v, w;
    edge() {}
    edge(int u, int v, int w) : u(u), v(v), w(w) {}
}e[MAXM];
int Bellman_Ford(int s, int n, int m, int k) {
    memset(dis, 0x3f, sizeof(dis));//把dis复制到dis_进行遍历松弛,不会产生串联
    dis[s] = 0;
    for (int i = 0; i < k; i++) {
        memcpy(dis_, dis, sizeof(dis));
        for (int j = 0; j < m; j++)
            if (dis_[e[j].u] < inf && dis[e[j].v] > dis_[e[j].u] + e[j].w)
                dis[e[j].v] = dis_[e[j].u] + e[j].w;
    }
    if (dis[n] < inf)
        return dis[n];
    return -1;
}
int main() {
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < m; i++)
        scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
    int cnt = Bellman_Ford(1, n, m, k);
    if (~cnt)
        printf("%d\n", cnt);
    else printf("impossible\n");
    return 0;
}