POJ3255次短路模板

模板级次短路问题

与最短路的区别在于，优先队列保存的对象不同，

队列中同时储存了

1：到某个点u的最短路+u到v的边

2：到某个点u的次短路+u到v的边

用这两种情况刷新最短路和次短路，所以temp=x.d+edge[i].dist

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<algorithm>
#define maxn 50100
#define maxm 1001000

using namespace std;
const int INF = 0x3f3f3f3f;

struct node				//s到u的距离d
{
	int d, u;
	friend bool operator<(node a, node b)
	{
		return a.d>b.d;
	}
	node(int dist, int point) :d(dist), u(point) {}
};

struct Edge
{
	int to, next;
	int dist;
}edge[maxm];
int head[maxn], tot;
int pre[maxn], dis[maxn], dis2[maxn];

void init()
{
	memset(head, -1, sizeof(head));
	tot = 0;
}

void addedge(int u, int v, int d)
{
	edge[tot].to = v;
	edge[tot].dist = d;
	edge[tot].next = head[u];
	head[u] = tot++;
}

void Dijkstra(int s)
{
	priority_queue<node> q;
	dis[s] = 0;

	while (!q.empty())
		q.pop();
	node a(0, s);
	q.push(a);       //起点入队列
	while (!q.empty())
	{	
		node x = q.top();
		q.pop();

		if (dis2[x.u]<x.d)   //最短路已找到
			continue;

		for (int i = head[x.u]; i != -1; i = edge[i].next)	//此时到u有新短路径，更新所有u开头的边的路径，i代表边的编号
		{	
			int v = edge[i].to;
			int temp = x.d + edge[i].dist;

			if (dis[v]>temp)
			{	
				swap(dis[v], temp);
				q.push(node(dis[v], v));
			}
			if (dis2[v]> temp && dis[v]<temp)
			{
				dis2[v] = temp;
				q.push(node(dis2[v], v));
			}
		}
	}
}


int main() {
	int n, r;
	while (~scanf("%d %d", &n, &r)) {
		init();

		for (int i = 1; i <= r; i++) {
			int u, v, d;
			scanf("%d %d %d", &u, &v, &d);
			addedge(u, v, d);
			addedge(v, u, d);
		}
		fill(dis + 1, dis + n + 1, 0x3f3f3f3f);
		fill(dis2 + 1, dis2 + n + 1, 0x3f3f3f3f);

		Dijkstra(1);
		printf("%d
", dis2[n]);
		
	}
}
/*
4 6
1 2 1
1 2 5
1 3 2
2 3 2
2 4 1
2 4 6
*/
/*
4 4
1 2 1
1 3 2
3 2 2
2 4 1
*/
/*
3 3
1 2 1
1 2 2
2 3 1
*/