POJ 3159 Candies——差分约束

POJ 3159 Candies——差分约束

题目中的关系可以抽象成为A->B的一条有向边，然后跑1~n的最短路即可（dijkstra）

#include #include #include #include #include using namespace std;const int INF = 0x3f3f3f3f;const int maxn = 3 * 1e5 + 10;int n, m, tot, head[maxn], dis[maxn];struct Node { int u, dis; Node(int uu, int dd) : u(uu), dis(dd) {} bool operator < (const Node &node) const { return dis > node.dis; }};struct Edge { int to, val, next;}edge[maxn];void addedge(int u, int v, int val) { tot++; edge[tot].to = v; edge[tot].val = val; edge[tot].next = head[u]; head[u] = tot;}int dijkstra(int s, int e) { for (int i = 1; i <= n; i++) dis[i] = INF; dis[s] = 0; priority_queue q; q.push(Node(s, 0)); while (!q.empty()) { Node node = q-(); q.pop(); int u = node.u; if (dis[u] < node.dis) continue; for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to, val = edge[i].val; if (dis[v] > dis[u] + val) { dis[v] = dis[u] + val; q.push(Node(v, dis[v])); } } } return dis[e];}int main() { scanf("%d %d", &n, &m); memset(head, -1, sizeof(head)); while (m--) { int u, v, val; scanf("%d %d %d", &u, &v, &val); addedge(u, v, val); } printf("%d\n", dijkstra(1, n)); return 0;}

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