POJ 3463 Sightseeing-白红宇

POJ 3463 Sightseeing

阅读量：6494 次

发布时间：2019-06-24

本文共 2052 字，大约阅读时间需要 6 分钟。

最短路+次短路（Dijkstra+priority_queue）

题意是要求你找出最短路的条数+与最短路仅仅差1的次短路的条数。

開始仅仅会算最短路的条数，和次短路的长度。真是给次短路条数跪了。ORZ。其它人都用Dijkstra。我想试试SPFA。

然后大神说要把这个最短，次短都拿去push。并且要用最短来。priority_queue。优先队列。妈蛋，这不是优先队列优化的Dijkstra么。

改得无比忧伤。反正開始改来改去连例子都过不了。

后来想着假设最短能够更新，原来的最短就变成次短了。

思路来了，刷刷就写完了。

WA……ORZ。

。。

最后对照大神的才知道。我push的仅仅有节点和长度。须要把标记也进去。

OOOOOOOOORZ。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #define INF 0x7fffffff#define eps 1e-6#define LL long longusing namespace std;int n,m;struct lx{ int v,len;};vector 
                
                  g[1001];struct node{ bool flag; int u; LL len; node(LL llen,int uu,bool fflag):len(llen),u(uu),flag(fflag){}};bool operator <(node a,node b){ return a.len>b.len;}void Dijkstra(int start,int thend){ bool vis[1001][2]; int cot[1001][2]; LL dis[1001][2]; for(int i=1; i<=n; i++) { for(int j=0;j<2;j++) dis[i][j]=INF,cot[i][j]=0,vis[i][j]=0;; } priority_queue
                 
                  q; q.push(node(0,start,0)); dis[start][0]=0; cot[start][0]=cot[start][1]=1; while(!q.empty()) { node now=q.top();q.pop(); int u=now.u;// printf("%lld %d %d==\n",now.len,now.u,now.flag); if(vis[u][now.flag])continue; vis[u][now.flag]=1; for(int j=0;j
                  
                   tmp) { dis[v][1]=dis[v][0]; cot[v][1]=cot[v][0]; dis[v][0]=tmp; cot[v][0]=cot[u][now.flag]; q.push(node(tmp,v,0)); q.push(node(dis[v][1],v,1)); } else if(dis[v][0]==tmp) cot[v][0]+=cot[u][now.flag]; else if(dis[v][1]>tmp) { dis[v][1]=tmp; cot[v][1]=cot[u][now.flag]; q.push(node(tmp,v,1)); } else if(dis[v][1]==tmp) cot[v][1]+=cot[u][now.flag]; } }// for(int i=1;i<=n;i++)// printf("%d :%lld-%lld\n",i,dis[i][0],dis[i][1]); if(dis[thend][0]+1!=dis[thend][1]) printf("%d\n",cot[thend][0]); else printf("%d\n",cot[thend][0]+cot[thend][1]);}int main(){ int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(int i=1; i<=n; i++) g[i].clear(); int u,v,len; lx now; while(m--) { scanf("%d%d%d",&u,&v,&len); now.v=v,now.len=len; g[u].push_back(now); } int start,thend; scanf("%d%d",&start,&thend); Dijkstra(start,thend); }}