POJ 1511 Invitation Cards——dijkstra

POJ 1511 Invitation Cards——dijkstra

数据太大，heap优化是必须的，然后不能用vector建图，即必须静态建图，因为数据太大动态建图会超时（有的提示RE），最后就是正反建图Dijkstra了，顺便一提SPFA又快又好写。。。。。。

#include #include #include using namespace std;typedef long long ll;const int INF = 0x3f3f3f3f;const int maxn = 1e6 + 10;int T, n, m, tot, head[2][maxn];ll dis[maxn];struct Node { int u, dis; Node(int x, int y) :u(x), dis(y) {} bool operator < (const Node &node) const { return node.dis < dis; }};struct Edge { int to, cost, next;}edge[2][maxn];void init() { tot = 0; for (int i = 1; i <= n; i++) head[0][i] = head[1][i] = -1;}void addedge(int flag, int u, int v, int cost) { edge[flag][tot].to = v; edge[flag][tot].cost = cost; edge[flag][tot].next = head[flag][u]; head[flag][u] = tot;}ll dijkstra(int flag) { for (int i = 1; i <= n; i++) dis[i] = INF; dis[1] = 0; priority_queue q; q.push(Node(1, 0)); while (!q.empty()) { Node node = q-(); q.pop(); int u = node.u; if (dis[u] < node.dis) continue; for (int i = head[flag][u]; i != -1; i = edge[flag][i].next) { int v = edge[flag][i].to, cost = edge[flag][i].cost; if (dis[v] > dis[u] + cost) { dis[v] = dis[u] + cost; q.push(Node(v, dis[v])); } } } ll ans = 0; for (int i = 1; i <= n; i++) { ans += dis[i]; } return ans;}int main() { scanf("%d", &T); while (T--) { scanf("%d %d", &n, &m); init(); for (int i = 1; i <= m; i++) { int u, v, cost; scanf("%d %d %d", &u, &v, &cost); ++tot; addedge(0, u, v, cost); addedge(1, v, u, cost); } ll ans = dijkstra(0) + dijkstra(1); printf("%I64d\n", ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。