Codeforces 1076D Edge Deletion(最短路瞎写)
题意 给一个无向简单联通图，删去边，留下最多k条边，问剩下的点里面从1开始的最短路距离不变的点最多怎么构造。
思路 这个思路特别特别简单，要不是我题目读错了我也不至于赛后被官方认定假算法给wa test3了，那我到底是写博客呢还是写博客呢。。。。
【Codeforces 1076D Edge Deletion(最短路瞎写)】我一开始以为是多源最短路的那种题，要求剩下的点到其他点的最短路尽量最少，我说，从最短路树上找个直径呗，然后如果边有多的，那就再加枝杈。结果最后比赛只剩2分钟，我枝杈都不加了，不管了，莽一发，万一过了呢？（肯定被hack，临时风光一下嘛）就过了。然后官方发公告说有些小孩用假算法过了我们等会就抓。第二天果然说的就是我。
实际上的正确思路只要跑一遍Dijkstra，然后从1开始BFS，如果边集大小小于k，就往里加。最后注意下数据范围需要long long，另外这题的数据3e5我估计朴素的Dijkstra会T，不知道有没有卡SPFA的数据。
代码
#include
#include
#include
#include
#include
using namespace std;
/*
* 潘骏同志的Dijsktra板子
* 本版是优化过的堆优化版
*/
struct edge
{
long long from;
long long to;
long long dist;
long long nxt;
long long num;
//其实也可以下标除以2，但我还是存了这个
edge(long long f,long long t,long long d,long long n,long long nu):from(f),to(t),dist(d),nxt(n),num(nu){}
};
vector edges;
//链式前向星，本来想用下标直接当边的编号的，但是无向图两条边事后觉得可以用下标除2
long long egs[300005];
void addedge(long long f,long long t,long long w,long long i)
{
edges.emplace_back(f,t,w,egs[f],i);
egs[f]=edges.size()-1;
edges.emplace_back(t,f,w,egs[t],i);
egs[t]=edges.size()-1;
}
long long dis[300005];
long long pre[300005];
//存储每个节点是被哪个边松弛了
long long lev[300005];
long long n,m;
long long k;
set ans;
long long dijsktra(long long s) {
memset(dis, 0x3f, sizeof(dis));
memset(pre, -1, sizeof pre);
memset(lev, 0, sizeof lev);
dis[s] = 0;
priority_queue, vector >, greater > > qq;
//堆顶是最小元素，按pair的first排序，所以把dis值放first（当年T到怀疑人生。。）
qq.push(make_pair(dis[s], s));
//源点入堆
while (!qq.empty()) {
long long preval = qq.top().first;
long long x = qq.top().second;
//和未优化的版本一样找最小元素
qq.pop();
if (dis[x] < preval) {
//如果目前的值已经比进堆时小了，就没必要再过一遍了，有的题会卡这个时间
continue;
}
for (long long j = egs[x];
j != -1;
j = edges[j].nxt) {
if (dis[edges[j].to] > dis[x] + edges[j].dist) {//一样的松弛操作，但是没有松驰过的点就没必要进堆了
dis[edges[j].to] = dis[x] + edges[j].dist;
pre[edges[j].to] = j;
lev[edges[j].to] = lev[x] + 1;
qq.push(make_pair(dis[edges[j].to], edges[j].to));
}
}
}
long long maxer = 0;
long long maxind = 0;
for (long long i = 1;
i <= n;
i++) {
if (lev[i] > maxer) {//本来拿来求最短路树直径的，现在没用了
maxer = lev[i];
maxind = i;
}
}
return maxind;
}
void bfs(long long s) {
queue qq;
qq.push(s);
while (!qq.empty()) {
long long now = qq.front();
qq.pop();
for (long long i = egs[now];
i != -1;
i = edges[i].nxt) {if (pre[edges[i].to] == i && ans.size() < k) {
//如果边集没满加最短路树上的边
ans.insert(edges[i].num);
qq.push(edges[i].to);
}
}
}
}
int main() {
cin >> n >> m >> k;
memset(egs, -1, sizeof egs);
edges.clear();
for (long long i = 1;
i <= m;
i++) {
long long a, b, c;
cin >> a >> b >> c;
addedge(a, b, c, i);
}
long long s = dijsktra(1);
//long long ender=dijsktra(s);
//本来用来求最短路树直径的，现在p用没有，注释了
ans.clear();
bfs(1);
//从源点1出发BFS最短路树
cout << ans.size() << endl;
for (auto it:ans) {
cout << it << " ";
}
cout << endl;
return 0;
}
