次短路 & dijkstra——P2865 [USACO06NOV] Roadblocks G
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define endl '\n'
#define int long long
typedef pair<int,int> PII;
const int N=5141;
const int M=1e5+1145;
const int INF=0x3f3f3f3f3f3f3f3f;
struct Edge{int to,val;
};
struct Node{int dis,pos;bool operator >(const Node& other)const{return dis>other.dis;}
};
vector<Edge>edge[N];
int n,m;
int dis1[N];
int dis2[N];void dijkstra_second_shortest(int start){//同一个点会被多次访问for(int i=1;i<=n;i++){dis1[i]=dis2[i]=INF;} dis1[start]=0;priority_queue<Node,vector<Node>,greater<Node> >pq;//存储到达 pos的又一种方式 //维护的是已知但未处理的路径信息**********pq.push({0,start});while(!pq.empty()){Node cur=pq.top();pq.pop();int pos=cur.pos;int cur_dis=cur.dis;if(cur_dis>dis2[pos])continue;for(const Edge& e:edge[pos]){int v=e.to;int new_dis=cur_dis+e.val;if(new_dis<dis1[v]){dis2[v]=dis1[v];dis1[v]=new_dis;pq.push({new_dis,v});} else if(dis1[v]<new_dis&&new_dis<dis2[v]){dis2[v]=new_dis;pq.push({new_dis,v});}}}
}signed main(){IOScin>>n>>m;for(int i=1;i<=m;i++){int a,b,d;cin>>a>>b>>d;edge[a].push_back({b,d});edge[b].push_back({a,d});}dijkstra_second_shortest(1);cout<<dis2[n]<<endl;return 0;
}