题目：路障Roadblocks
思路：
次短路模板。
正反求最短路dist1[x]和dist2[x]，表示1到x的最短路和x到1的最短路。
枚举每条边更新答案。
注意：priority_queue是大根堆！<运算符不能定义错！
代码：
#include<bits/stdc++.h>
using namespace std;#define maxn 5000
#define maxm 100000
#define read(x) scanf("%d",&x)struct Edge{
int x,y,z;Edge(){
}Edge(int xx,int yy,int zz) {
x=xx,y=yy,z=zz;}
};struct Pair{
int y,z;Pair(){
}Pair(int yy,int zz) {
y=yy,z=zz;}bool operator < (const Pair& oth) const {
return z>oth.z;}
};int n,m;
vector<Edge> g[maxn+5];int dist1[maxn+5],dist2[maxn+5];
priority_queue<Pair> que;
bool vis[maxn+5];Edge e[maxm+5];void dijkstra(int s,int t,int* dist) {
priority_queue<Pair> emp;que=emp;for(int i=1;i<=n;i++) if(i!=s) dist[i]=1e9; que.push(Pair(s,0));memset(vis,0,sizeof(vis));while(!que.empty()) {
int h=que.top().y;que.pop();if(vis[h]) continue;vis[h]=true;for(int i=0;i<g[h].size();i++) {
int x=g[h][i].y,z=g[h][i].z;if(dist[x]>dist[h]+z) {
dist[x]=dist[h]+z;que.push(Pair(x,dist[x]));}}}
}int main() {
read(n),read(m);for(int i=1;i<=m;i++) {
int x,y,z;read(x),read(y),read(z);g[x].push_back(Edge(x,y,z));g[y].push_back(Edge(y,x,z));e[i]=Edge(x,y,z);}dijkstra(1,n,dist1);dijkstra(n,1,dist2);int d=dist1[n],ans=1e9; for(int i=1;i<=m;i++) {
int d1=dist1[e[i].x]+dist2[e[i].y]+e[i].z;int d2=dist2[e[i].x]+dist1[e[i].y]+e[i].z;if(d1<ans&&d1!=d) ans=d1;if(d2<ans&&d2!=d) ans=d2;}printf("%d",ans);return 0;
}