POJ 3255 Roadblocks 次短路

题目大意：

有N条道路和N个路口，道路是双向的，问1号路口到N号路口的次最短路径是多少？次最短路径是比最短路径长的次短的路径。同一条边可已经过多次。

思路：

最短路和次短路不会重合，而次短路可以从最短路的某个点绕一个点得到。为啥是一个点？如果绕两个点的话会比绕一个点来的长，就不会是次短路了。

先对1和n为源点进行两次dijkstra，接下来枚举每条边，则可以算出此时的和temp=dis1[from]+disn[to]+val;或者temp=disn[from]+dis1[to]+val;如果不等于最短路则取最小值。

#include
  
   
#include
   
     #include
    
      #include
     
       using namespace std; const int MAXN=5000+10; const int MAXM=200000+10; const int INF=0x3fffffff; int n,r,head[MAXN],len,dis1[MAXN],disn[MAXN]; struct edge { int to,val,next; }e[MAXM]; void add(int from,int to,int val) { e[len].to=to; e[len].val=val; e[len].next=head[from]; head[from]=len++; } struct node { int id,val; node(int id,int val):id(id),val(val){} bool operator < (const node &x)const{ return val>x.val; } }; void dijkstra(int *dis,int s) { for(int i=1;i<=n;i++) dis[i]=INF; dis[s]=0; priority_queue
      
        q; q.push(node(s,0)); while(!q.empty()) { int cur=q.top().id,val=q.top().val; q.pop(); for(int i=head[cur];i!=-1;i=e[i].next) { int id=e[i].to; if(dis[id] > dis[cur]+e[i].val) { dis[id]=dis[cur]+e[i].val; q.push(node(id,dis[id])); } } } } int main() { while(~scanf(%d%d,&n,&r)) { memset(head,-1,sizeof(head)); len=0; for(int i=0;i