【自用】关于严格次短路

#include<bits/stdc++.h>
#include<queue>
using namespace std;
int n,r,p1[5002],p2[5002];
vector<pair<int,int> > G[5002]; 
priority_queue<pair<int,int> > q;
int main(){
	cin>>n>>r;
	for(int i=1;i<=n;i++)p1[i]=p2[i]=1073741823;
	for(int i=1;i<=r;i++){
		int u,v,w;
		cin>>u>>v>>w;
		G[u].push_back(make_pair(w,v));
		G[v].push_back(make_pair(w,u));
	}
	q.push(make_pair(0,1));
	p1[1]=0;
	while(!q.empty()){
		pair<int,int> pr=q.top();
		q.pop();
		int u=pr.second,z=pr.first;
		if(z>p2[u])continue;
		for(int i=0;i<G[u].size();i++){
			int v=G[u][i].second,w=G[u][i].first;
			if(p1[u]+w<=p1[v]){
				p1[v]=p1[u]+w;
				q.push(make_pair(p1[v],v));
			}
			else if(p1[u]+w<p2[v]){
				p2[v]=p1[u]+w;
				q.push(make_pair(p2[v],v));
			}
			if(p2[u]+w<p2[v]){
				p2[v]=p2[u]+w;
//				q.push(make_pair(p2[v],v));
			}
		}
	}
	cout<<p2[n]<<endl;
	return 0;
}