AcWing第2场周赛 — C.边的删减

题目链接

题面

给定一个由 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≤10⁵,1≤m≤10⁵,n−1≤m,0≤k≤m,1≤x,y≤n,x≠y,1≤w≤10⁹。

输入样例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

题解

dijkstra，dfs

最多保留 k 条边，及最多保留 k + 1 个点，然后使得剩余点为最短路径树上的点即可满足题意。

则我们先用 dijkstra 跑出全图到点 1 的最短路径，然后从点 1 出发，深搜前 k 条最短路径上的边即可。

代码

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

const int N = 1e5 + 5, M = 2e5 + 5;
typedef long long LL;
typedef pair<LL, int> PII;
int n, m, k, tot;
int head[N], ver[M], edge[M], Next[M], id[M];
LL d[N];
bool v[N];
vector<int> ans;

void add(int x, int y, int z, int d){
    ver[++tot] = y;
    edge[tot] = z;
    Next[tot] = head[x];
    head[x] = tot;
    id[tot] = d;
}

void dijkstra(){
    memset(v, false, sizeof v);
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> q;
    q.push({0, 1});
    
    while(q.size()){
        int x = q.top().second;
        q.pop();
        if(v[x]) continue;
        v[x] = true;
        
        for(int i = head[x]; i; i = Next[i]){
            int y = ver[i], z = edge[i];
            if(d[y] > d[x] + z){
                d[y] = d[x] + z;
                q.push({d[y], y});
            }
        }
    }
}

void dfs(int x){
    v[x] = true;
    for(int i = head[x]; i; i = Next[i]){
        int y = ver[i], z = edge[i];
        if(!v[y] && d[y] == d[x] + z){
            if(ans.size() < k) ans.push_back(id[i]);
            dfs(y);
        }
    }
}

int main(){
    cin >> n >> m >> k;
    for(int i = 1, x, y, z; i <= m; i++){
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z, i);
        add(y, x, z, i);
    }
    
    dijkstra();
    memset(v, 0, sizeof v);
    dfs(1);
    printf("%d\n", ans.size());
    for(int x:ans) printf("%d ", x);
    puts("");
    
    return 0;
}