Edge|Edge Deletion CodeForces - 1076D（水最短路） EdgeDeletionCodeForces-1076D（水最短

题意：
设从1到每个点的最短距离为d，求删除几条边后仍然使1到每个点的距离为d，使得剩下的边最多为k
解析：
先求来一遍spfa，然后bfs遍历每条路，如果d[v] == d[u] + Node[i].w 则说明这条路要保留
注意是按着走的路的顺序输出的 wa1
【Edge|Edge Deletion CodeForces - 1076D（水最短路）】注意最大值设为0x3fwa3学到了。。。emm 用memset设置数组为0x3f是无穷大

#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define rap(i, a, n) for(int i=a; i<=n; i++) #define rep(i, a, n) for(int i=a; i=a; i--) #define lep(i, a, n) for(int i=n; i>a; i--) #define rd(a) scanf("%d", &a) #define rlld(a) scanf("%lld", &a) #define rc(a) scanf("%c", &a) #define rs(a) scanf("%s", a) #define rb(a) scanf("%lf", &a) #define rf(a) scanf("%f", &a) #define pd(a) printf("%d\n", a) #define plld(a) printf("%lld\n", a) #define pc(a) printf("%c\n", a) #define ps(a) printf("%s\n", a) #define MOD 2018 #define LL long long #define ULL unsigned long long #define Pair pair #define mem(a, b) memset(a, b, sizeof(a)) #define _ios_base::sync_with_stdio(0),cin.tie(0) //freopen("1.txt", "r", stdin); using namespace std; const int maxn = 2222222, INF = 0x7fffffff; int head[maxn], vis[maxn], nex[maxn]; LL d[maxn]; int cnt, n, m, s, t, k; vector g; struct node { int u, v; LL w; }Node[maxn]; void add_(int u, int v, int w) { Node[cnt].u = u; Node[cnt].v = v; Node[cnt].w = w; nex[cnt] = head[u]; head[u] = cnt++; }void add(int u, int v, int w) { add_(u, v, w); add_(v, u, w); }int spfa() { mem(d, 0x3f); deque Q; Q.push_front(s); d[s] = 0; vis[s] = 1; while(!Q.empty()) { int u = Q.front(); Q.pop_front(); vis[u] = 0; for(int i = head[u]; i != -1; i = nex[i]) { int v = Node[i].v; if(d[v] > d[u] + Node[i].w) { d[v] = d[u] + Node[i].w; if(!vis[v]) { if(Q.empty()) Q.push_front(v); else { if(d[v] < d[Q.front()]) Q.push_front(v); else Q.push_back(v); } vis[v] = 1; } } } } }void init() { mem(head, -1); g.clear(); cnt = 0; }void bfs() { queue Q; Q.push(1); mem(vis, 0); vis[1] = 1; int cnt1 = 0; while(!Q.empty()) { int u = Q.front(); Q.pop(); for(int i = head[u]; i != -1; i = nex[i]) { int v = Node[i].v; if(d[v] == d[u] + Node[i].w) { if(!vis[v]) { g.push_back((i + 2) / 2); vis[v] = 1; Q.push(v); if(++cnt1 == k) return; } } } } }int main() { //cout << 0x3f <> n >> m >> k; for(int i = 0; i < m; i++) { cin >> u >> v >> w; add(u, v, w); } if(k == 0) return puts("0"); s = 1; spfa(); bfs(); cout << g.size() << endl; for(int i = 0; i < g.size(); i++) cout << g[i] << " "; cout << endl; return 0; }