题目描述

本题给定一个无向连通加权图，从第 1 个点出发到第 i 个点的最短距离记为 di

接着我们需要进行操作，删掉图中的一些边，最多保留原图中的 k 条边

删完边后，如果点 i 到点 1 的距离任然是原图的中最短路长度，则我们称该点为优秀点

我们需要找出一种删边方案，使得最终图中有尽可能多的 优秀点

分析

对于初始图，我们需要得到每个点 i 到起始点 1 的最短路径长度，这毫无疑问会让我们想到最短路算法

因此，一开始我们需要挑选一个最短路算法来求每个点到起点的最短路径

接着看下一个要求，我们要找出一个保留小于等于 k 条边的方案，使得构成最短路的点尽可能多

为了保证我们保留下来的边是有价值的，因此我们保留的边一定是更新出最短路的边

而 $\mathrm{Dijkstra 算法}$ 的贪心思想是：每次更新到起点距离最短的点的最短路长度

利用该性质，我们知道：
$\mathrm{Dijkstra 算法}$ 对于每轮更新出最短路的点来说，最后一次更新他距离的边一定是 有价值的

这些有价值的边，连成的点就构成了一个最短路树

因此我们直接用 Dijkstra 求一遍最短路的同时，把每个点最后一次被更新最短距离的边都存下来

于是被保留下来边，一定是有价值的边

从前往后（不从前往后保留，就不在一个连通块里，那这样的边也是没价值的），把这些边保留下来即可

注意：本题的边长是 $10^9$，因此最短路的长度可能会爆 int ，需要用 long long 来存路径长度

Code

时间复杂度：$O(m\log n)$ 堆优化版Dijkstra

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

#define x first
#define y second

using namespace std;

typedef long long LL;

typedef pair<pair<LL,int>,int> PIII;

const int N = 1e5 + 10, M = 2 * N;

int n, m, k;
int h[N], e[M], ne[M], w[M], idx;
LL dist[N];
bool st[N];
int res[M], cnt;

void add(int a, int b, int c)  // 添加一条边a->b，边权为c
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void dijkstra()  // 求1号点到n号点的最短路距离
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PIII, vector<PIII>, greater<PIII>> heap;
    heap.push({{0, 1}, -1});

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.x.y, distance = t.x.x;
        int edg = t.y;

        if (st[ver]) continue;
        st[ver] = true;
        res[cnt ++ ] = edg;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({{dist[j], j}, i});
            }
        }
    }
}
int main()
{
    memset(h, -1, sizeof h);
    scanf("%d%d%d", &n, &m, &k);
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
        add(b, a, c);
    }
    dijkstra();
    cout << min(cnt - 1, k) << endl;
    for (int i = 1; i < min(cnt, k + 1); ++ i) cout << res[i] / 2 + 1 << " ";
    return 0;
}