最短路径树

2023-12-01 11:08:58

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

设点 11 到点 ii 的最短路径长度为 didi。

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

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

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

输入格式

第一行包含三个整数 n,m,kn,m,k。

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

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

输出格式

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

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

按输入顺序，所有边的编号从 11 到 mm。

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

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

数据范围

对于前五个测试点，2≤n≤15,1≤m≤152≤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≤1092≤n≤105,1≤m≤105,n−1≤m,0≤k≤m,1≤x,y≤n,x≠y,1≤w≤109。

输入样例1：

输出样例1：

2
1 2

输入样例2：

输出样例2：

2
3 2

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef pair<LL, int> PII;
const int N =100010,M=200010;
int n,m,k;
int h[N], e[M], ne[M],w[M],id[M],idx;
LL dist[N];
bool st[N];
vector<int> ans;
void add(int a, int b, int c,int d)  // 添加一条边a->b，边权为c
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], id[idx]=d, h[a] = idx ++ ;
}
void dijkstra()  // 求1号点到n号点的最短路距离
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});

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

        int ver = t.second, distance = t.first;

        if (st[ver]) continue;
        st[ver] = true;

        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});
            }
        }
    }
}
void dfs(int u){
    st[u]=true;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
       // cout<<j<< ' ';
       // cout<<st[j]<<' ';
        if(!st[j] && dist[j]==dist[u]+w[i])
        {
           // cout<<j<<' ';
            if(ans.size()<k)ans.push_back(id[i]);
           // cout<<id[i]<<' ';
            dfs(j);
        }
    }
}
int main()
{
    scanf("%d%d%d", &n, &m, &k);
  //  memset(st, 0, sizeof st);
  //  cout<<st[2];
    memset(h, -1, sizeof h);
  //  cout<<st[2];
    for(int i=1;i<=m;i++){
        int a,b,c;
        scanf("%d%d%d", &a,&b,&c);
        add(a,b,c,i);
        add(b,a,c,i);
      //  cout<<a<<' '<<b<<' '<<c;
    }
    cout<<st[2];
    dijkstra();
   // cout<<st[2];
    memset(st, 0, sizeof st);
    dfs(1);
    printf("%d\n",ans.size());
    for(auto x:ans)printf("%d ",x);
    return 0;
}

码农公寓