POJ 3255 Roadblocks——次短路

POJ 3255 Roadblocks——次短路

​​这个博主写得很清楚​​

#include #include #include #include #include #include using namespace std;typedef pair P;const int maxn = 1e4;const int maxm = 250000;const int INF = 0x3f3f3f3f;int n, m, tot, head[maxn];long long dis1[maxn], dis2[maxn];struct Edge { int to, cost, next; }edge[maxm];void init() { tot = 0; memset(head, -1, sizeof(head));}void addedge(int u, int v, int cost) { edge[++tot].to = v; edge[tot].cost = cost; edge[tot].next = head[u]; head[u] = tot;}long long dijkstra(int s) { memset(dis1, INF, sizeof(dis1)); memset(dis2, INF, sizeof(dis2)); dis1[s] = 0; priority_queue, greater

> q; q.push(make_pair(0, s)); while (!q.empty()) { int u = q.top().second, t = q.top().first; q.pop(); if (dis2[u] < t) continue; for (int i = head[u]; ~i; i = edge[i].next) { int v = edge[i].to, cost = edge[i].cost; if (dis1[v] > t + cost) { if (dis2[v] > dis1[v]) { dis2[v] = dis1[v]; q.push(make_pair(dis2[v], v)); } dis1[v] = t + cost; q.push(make_pair(dis1[v], v)); } else if (dis1[v] < t + cost){ if (dis2[v] > t + cost) { dis2[v] = t + cost; q.push(make_pair(dis2[v], v)); } } } } return dis2[n];}int main() { while (~scanf("%d %d", &n, &m)) { init(); int u, v, cost; for (int i = 1; i <= m; i++) { scanf("%d %d %d", &u, &v, &cost); addedge(u, v, cost); addedge(v, u, cost); } printf("%lld\n", dijkstra(1)); } return 0;}

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