Lucien

Codeforces 1076D - Edge Deletion - 思维
Codeforces 1076D - Edge Deletion - 思维题解链接https://lucien.i...

22
2018/12

# Codeforces 1076D - Edge Deletion - 思维

## 题解链接

https://lucien.ink

## 题目链接

http://codeforces.com/contest/1076/problem/D

## 实现

https://pasteme.cn/2742

#include <bits/stdc++.h>
const int maxn = int(3e5) + 7;
typedef long long ll;
std::pair<int, int> pre[maxn];
std::vector<std::pair<int, int>> tree[maxn];
std::vector<int> ans;
struct { int next, v, cost, index; } edge[maxn << 1];
struct Graph {
void addedge(int u, int v, int cost, int index) {
edge[cnt] = {head[u], v, cost, index};
}
} graph;
int n, m, k, cnt;
namespace Dijkstra {
ll dist[maxn];
bool vis[maxn];
struct Node {
int u;
ll dist;
Node(int u, ll dist):u(u), dist(dist) {}
bool operator < (const Node &tmp) const {
return dist > tmp.dist;
}
};
void run() {
std::priority_queue<Node> que;
que.emplace(1, 0);
memset(dist, 0x3f, sizeof(dist));
dist[1] = 0;
while (!que.empty()) {
int u = que.top().u;
que.pop();
if (vis[u]) continue;
vis[u] = true;
for (int i = graph.head[u]; ~i; i = edge[i].next) {
int v = edge[i].v, cost = edge[i].cost, index = edge[i].index;
if (dist[v] > dist[u] + cost) {
dist[v] = dist[u] + cost;
que.emplace(v, dist[v]);
pre[v] = std::make_pair(u, index);
}
}
}
}
}
void dfs(int u) {
for (auto it : tree[u]) {
if (cnt++ < k) {
ans.push_back(it.second);
dfs(it.first);
}
}
}
int main() {
#ifdef AC
freopen("../in", "r", stdin);
#endif
std::cin >> n >> m >> k;
for (int i = 1, u, v, cost; i <= m; i++) {
std::cin >> u >> v >> cost;