OJ题号：洛谷2951

思路：Dijkstra+堆优化。注意是无向图，所以加边时要正反各加一遍。

1 #include
     
       2 #include
      
        3 #include
       
         4 #define dis first 5 #define to second 6 const int N=20001,inf=0x7fffffff; 7 typedef std::pair
        
          Edge; 8 int n,m,d[N]; 9 std::vector
         
           e[N];10 void add(int a,int b) {11     e[a].push_back(b);12 }13 void dijkstra() {14     __gnu_pbds::priority_queue
          
           
             > q;15 __gnu_pbds::priority_queue
            
             
               >::point_iterator a[n+1];16 for(int i=1;i<=n;i++) {17 a[i]=q.push((i==1)?(Edge){ 0,i}:(Edge){inf,i});18 d[i]=(i==1)?0:inf;19 }20 while(!q.empty()) {21 Edge x=q.top();22 q.pop();23 if(x.dis==inf) continue;24 int u=x.to;25 for(std::vector
              
               ::iterator i=e[u].begin();i
               
                dis) {47 id=i;48 dis=d[i];49 count=1;50 }51 }52 printf("%d %d %d\n",id,dis,count);53 return 0;54 }