题目链接：https://codeforces.com/problemset/problem/1076/D
题意：给你一个n个点，m条边的DAG图，边为双向边，没有重边。现在最多保留k条边，怎么使得好点个数最多。
好点定义为：在原图中1到该点距离和只保留某一些边后的图中1到该点距离不变的点。先输出保留边的个数，然后输出这些保留的边的编号（1~m）。
思路：dijkstra是基于贪心思想的，所以其贪心选择的前k条边一定是需要保留的。记得开long long。
#include
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 E[maxn];
vector 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 > 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("%d\n",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 （最短路+思维）】
