题目链接：
https://vjudge.net/problem/POJ-3255
题目大意：
给无向图，求1到n的次短路长度
思路：
由于边数较多，应该使用dijkstra的队列优化
用d数组存储最短路，用d2数组存储次短路，每次更新的时候，先松弛更新最短路，如果松弛更新成功，把之前的最短路取出，再和次短路比较，更新次短路。每次更新两个数组
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
typedef pair<int, int> Pair;
const int maxn = + ;
const int INF = 0x3f3f3f3f;
int n, m;
struct edge
{
int v, w;
edge(int v, int w):v(v), w(w){}
};
vector<edge>G[maxn];
int d[maxn], d2[maxn];
void dijkstra()
{
memset(d, INF, sizeof(d));
memset(d2, INF, sizeof(d2));
d[] = ;
priority_queue<Pair, vector<Pair>, greater<Pair> >q;
q.push(Pair(, ));//1为当前节点，0位最短距离
while(!q.empty())
{
Pair now = q.top();
q.pop();
int dis = now.first, u = now.second;
//cout<<dis<<" "<<u<<endl;
if(dis > d2[u])continue;//距离比次短距离大，直接continue
for(int i = ; i < G[u].size(); i++)
{
edge &e = G[u][i];
int dis2 = dis + e.w;
if(d[e.v] > dis2)
{
swap(d[e.v], dis2);//dis2保存较小的值和后面进行比较
q.push(Pair(d[e.v], e.v));
}
if(d2[e.v] > dis2 && d[e.v] < dis2)//保证dis2为次短路
{
d2[e.v] = dis2;
q.push(Pair(d2[e.v], e.v));//次短路也入队列
}
}
}
cout<<d2[n]<<endl;
}
int main()
{
cin >> n >> m;
int u, v, w;
while(m--)
{
scanf("%d%d%d", &u, &v, &w);
G[u].push_back(edge(v, w));
G[v].push_back(edge(u, w));
}
dijkstra();
}