题目描述

给定一个由 n 个点和 m 条边组成的无向连通加权图。

设点 1 到点 i 的最短路径长度为 di。

现在，你需要删掉图中的一些边，使得图中最多保留 k 条边。

如果在删边操作全部完成后，点 1 到点 i 的最短路径长度仍为 di，则称点 i 是一个优秀点。

你的目标是通过合理进行删边操作，使得优秀点的数量尽可能大。

输入格式
第一行包含三个整数 n,m,k。

接下来 m 行，每行包含三个整数 x,y,w，表示点 x 和点 y 之间存在一条长度为 w 的边。

保证给定无向连通图无重边和自环。

输出格式
第一行包含一个整数 e，表示保留的边的数量 (0≤e≤k)。

第二行包含 e 个不同的 1∼m 之间的整数，表示所保留的边的编号。

按输入顺序，所有边的编号从 1 到 m。

你提供的方案，应使得优秀点的数量尽可能大。

如果答案不唯一，则输出任意满足条件的合理方案均可。

数据范围
对于前五个测试点，2≤n≤15,1≤m≤15。
对于全部测试点，2≤n≤105,1≤m≤105,n−1≤m,0≤k≤m,1≤x,y≤n,x≠y,1≤w≤109。

样例

输入样例1：
3 3 2
1 2 1
3 2 1
1 3 3
输出样例1：
2
1 2
输入样例2：
4 5 2
4 1 8
2 4 1
2 1 3
3 4 9
3 1 5
输出样例2：
2
3 2

算法1

(dijkstra) $O(n^2)$

求dist时，记录好结点的前驱结点

从1开始求
则可以找出，从1开始的最短路径们

刚来acwiing，还没学习课程。不会用板子
就按照自己的理解写的
python3 TLE
c++ MLE
但思路应该是对的

时间复杂度

参考文献

python3 代码

from collections import defaultdict
import heapq

[n, m, k] = [int(x) for x in input().split()]

eID = 1             #边的ID号
edge = [[(-1,-1) for _ in range(n + 1)] for _ in range(n + 1)]  #邻接矩阵
adjvex = defaultdict(list)                                      #邻接表
for _ in range(m):
    x, y, w = map(int, input().split())
    edge[x][y] = (w, eID)
    edge[y][x] = (w, eID)
    adjvex[x].append(y)
    adjvex[y].append(x)
    eID += 1

INF = 10 ** 9
dist = [INF for _ in range(n + 1)]
pre = [-1 for _ in range(n + 1)]

#--------- 单源最短路径算法 dijkstra算法-----------#
def dijkstra() -> None:
    visited = [False for _ in range(n + 1)]
    dist[1] = 0     #结点编号从1开始
    minHeap = []
    heapq.heappush(minHeap, (0, 1))
    while minHeap:          #候选区
        d, x = heapq.heappop(minHeap)
        if visited[x] == True:      #已经在已选区域
            continue
        visited[x] = True           #正式加入已选的区域
        for y in adjvex[x]:
            if dist[y] > dist[x] + edge[x][y][0]:
                dist[y] = dist[x] + edge[x][y][0]
                heapq.heappush(minHeap, (dist[y], y))
                pre[y] = x


dijkstra()          #求从1出发，到各点的最短距离


nxt = defaultdict(set)      #最短路径上，结点的后一结点
for y in range(1, n + 1):
    if pre[y] != -1:
        x = pre[y]
        nxt[x].add(y)


res = []
seen = [False for _ in range(n + 1)]

def dfs(x: int) -> None:
    seen[x] = True
    for y in nxt[x]:
        if seen[y] == False and dist[y] == dist[x] + edge[x][y][0]:
            if len(res) < k:
                res.append(edge[x][y][1])
                dfs(y)

dfs(1)

print(len(res))
for x in res:
    print(x, end = ' ')

C++ 代码

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n;    cin >> n;
    int m;    cin >> m;
    int k;    cin >> k;
    vector<vector<pair<int,int>>> edge(n + 1, vector<pair<int,int>>(n + 1));
    unordered_map<int,unordered_set<int>> adjvex;
    int eID = 1;
    for (int _ = 0; _ < m; _ ++)
    {
        int x;    cin >> x;
        int y;    cin >> y;
        int w;    cin >> w;
        edge[x][y] = pair<int,int>{w, eID};
        edge[y][x] = pair<int,int>{w, eID};
        adjvex[x].insert(y);
        adjvex[y].insert(x);
        eID ++;
    }

    int INF = 1e9 + 7;
    vector<int> dist(n + 1, INF);
    vector<int> pre(n + 1,  -1);

    std::function<void()> dijkstra = [&] ()
    {
        vector<bool> visited(n + 1, false);
        dist[1] = 0;
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> minHeap;
        minHeap.push({0, 1});
        while (minHeap.size())
        {
            auto [d, x] = minHeap.top();    minHeap.pop();
            if (visited[x])
                continue;
            visited[x] = true;
            for (int y: adjvex[x])
            {
                if (dist[x] + edge[x][y].first < dist[y])
                {
                    dist[y] = dist[x] + edge[x][y].first;
                    minHeap.push({dist[y], y});
                    pre[y] = x;
                }
            }
        }
    };

    dijkstra();

    unordered_map<int,unordered_set<int>> nxt;
    for (int y = 1; y < n + 1; y ++)
        if (pre[y] != -1)
            nxt[pre[y]].insert(y);

    vector<int> res;
    vector<bool> seen(n + 1, false);

    std::function<void(int)> dfs = [&] (int x)
    {
        seen[x] = true;
        for (int y : nxt[x])
        {
            if (seen[y] == false && dist[y] == dist[x] + edge[x][y].first)
            {
                if (res.size() < k)
                {
                    res.push_back(edge[x][y].second);
                    dfs(y);
                }
            }
        }
    };

    dfs(1);

    cout << res.size() <<  endl;
    for (int x: res)
        cout << x << ' ';
    cout << endl;

    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla