Codeforces - 1076D - Edge Deletion （最短路+思维）

题目链接：https://codeforces.com/problemset/problem/1076/D

题意：给你一个n个点，m条边的DAG图，边为双向边，没有重边。现在最多保留k条边，怎么使得好点个数最多。
好点定义为：在原图中1到该点距离和只保留某一些边后的图中1到该点距离不变的点。先输出保留边的个数，然后输出这些保留的边的编号（1~m）。

思路：dijkstra是基于贪心思想的，所以其贪心选择的前k条边一定是需要保留的。记得开long long。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn = 4e5+10;
const ll inf = 0x3f3f3f3f3f3f3f3f;
struct node{int b, id; ll x;}v;
int p[maxn];
bool vis[maxn];
vector <node> E[maxn];
vector <int> ans;
int n, m, k; ll d[maxn];
void init()
{
    for(int i = 0; i <= n; i++)
    {
        E[i].clear(); ans.clear();
        d[i] = inf; vis[i] = false;
    }
}
void dijkstra()
{
    d[1] = 0;
    priority_queue<pair <ll, int> > Q;
    Q.push(make_pair(-d[1],1));
    while(!Q.empty() && ans.size() <= k)
    {
        int now = Q.top().second;
        Q.pop();
        if(vis[now]) continue;
        vis[now] = true;
        ans.push_back(p[now]);
        for(int i = 0; i < E[now].size(); i++)
        {
            int v = E[now][i].b;
            if(!vis[v] && d[v] > d[now] + E[now][i].x)
            {
                p[v] = E[now][i].id;
                d[v] = d[now] + E[now][i].x;
                Q.push(make_pair(-d[v],v));
            }
        }
    }
}
int main()
{
    while(~scanf("%d%d%d",&n, &m, &k))
    {
        init();
        for(int i = 1; i <= m; i++)
        {
            int a, b; ll x;
            scanf("%d%d%lld",&a,&b,&x);
            v.b = b, v.x = x, v.id = i;
            E[a].push_back(v); v.b = a;
            E[b].push_back(v);
        }
        dijkstra();
        printf("%dn",ans.size() - 1);
        for(int i = 1; i < ans.size(); i++)
            printf("%d%c",ans[i],i == ans.size() - 1 ? 'n' : ' ');
    }
}

最后

以上就是专注刺猬为你收集整理的Codeforces - 1076D - Edge Deletion （最短路+思维）的全部内容，希望文章能够帮你解决Codeforces - 1076D - Edge Deletion （最短路+思维）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。