题目描述

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

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

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

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

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

输入格式

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

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

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

输出格式

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

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

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

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

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

样例

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

数据范围

对于前五个测试点，$2≤n≤15,1≤m≤15$。
对于全部测试点，$2≤n≤10^5,1≤m≤10^5,n−1≤m,0≤k≤m,1≤x,y≤n,x≠y,1≤w≤10^9$。

算法1

(spfa)

与dij相似

C++ 代码

#include <bits/stdc++.h>
using namespace std;
int lu[200005],x,k,y,z,idx,cost[200005],ne[200005],head[200005],go[200005],n,m;
bool f[200005];
long long g[200005];
queue<int>q;
vector<int>ans;
inline void add(int x,int y,int z,int d)
{
    ne[++idx]=head[x];
    head[x]=idx;
    go[idx]=y;
    lu[idx]=d;
    cost[idx]=z;
}
inline void spfa(int s)
{
    memset(f,0,sizeof(f));
    q.push(1);
    f[s]=1;
    memset(g,0x3f,sizeof(g));
    g[s]=0;
    while(!q.empty())
    {
        x=q.front();
        f[x]=0;
        q.pop();
        for(int j=head[x];j;j=ne[j])
        {
            y=go[j];
            if(g[y]>g[x]+cost[j])
            {
                g[y]=g[x]+cost[j];
                if(!f[y])
                {
                    q.push(y);
                    f[y]=1;
                }
            }
        }
    }
}
void dfs(int x)
{
    f[x]=1;
    for(int i=head[x];i;i=ne[i])
    {
        y=go[i];
        if(!f[y]&&g[y]==g[x]+cost[i])
        {
            if(ans.size()<k)
            ans.push_back(lu[i]);
            dfs(y);
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>z;
        add(x,y,z,i);
        add(y,x,z,i);
    }
    spfa(1);
    dfs(1);
    cout<<ans.size()<<endl;
    for(int i=0;i<ans.size();i++)
    cout<<ans[i]<<' ';
}