更改Bellman算法使得其不仅能够得到最短路，还能得到最短路的数量，请给出伪代码。重复计数问题。
``#include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;

const int N = 510, M = 1e5 + 10;

struct Edge
{
int a, b, c;
}edges[M];
int n, m, k;
int path[N], cnt[N], dist[N], backup[N];
set[HTML_REMOVED] contains[N];
// dist、backup用于求解最短路
// path数组用于求解具体的最短路路径
// cnt用于记录每个点最短路的数量，contains辅助cnt的填表去重

// 1.状态表示：cnt[i]表示所有到i点的满足题目条件最短路的个数
// 2.状态转移：cnt[i] =
// 2.1如果dist被更新则等于更新它的那个点的cnta
// 2.2如果dist在松弛时相等则说明有两种情况
// 2.2.1 到i点的这个点的dist不在发生变化但在后序过程中还有遍历（也是spfa的优化点）这时如果简单的让cnt[i] += cnt[a]由于在之前某次边集遍历中该点的cnt已经被计算于是会重复计算，此处可以对于每一个点维护一个set记录所有被计数的路径中的最后一个点，在后续只需判断是否在set即可，如果a在且距离变小则需更新disti同时请客set重新计算cnt
// 2.2.2 上述2.2.1的相反，还没有计算则cnt[i] += cnt[a]

void bellman()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0, path[1] = 0, cnt[1] = 1;

for (int i = 0; i < k; i++)
{
    memcpy(backup, dist, sizeof dist);
    for (int j = 0; j < m; j++)
    {
        int a = edges[j].a, b = edges[j].b, c = edges[j].c;
        if (dist[b] > backup[a] + c)
        {
            dist[b] = backup[a] + c;
            path[b] = a;
            cnt[b] = cnt[a];

            contains[b].clear();
            contains[b].insert(a);
        } else if (dist[b] == backup[a] + c)
        {
            // 由于cnt[i]的状态表示为：从源点到i的所有满足要求的最短路的个数，因此当更新时发现权值相同简单得➕cnt[a]]会导致当该点在后续松弛过程中不再更新dist时还会重复计算cnt，考虑到dp填表的思路，只需对填cnt表的上一步采用set去重即可
            if (contains[b].find(a) == contains[b].end()) cnt[b] += cnt[a], contains[b].insert(a);
        }
    }
}

if (dist[n] > 0x3f3f3f3f / 2) puts("impossible");
else cout << dist[n] << endl;

}

int main()
{
cin >> n >> m >> k;
for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
edges[i] = {a, b, c};
}

bellman();
return 0;

}``