1 #include
      
        2 #include
       
         3 #define INF 1000000 4 using namespace std; 5 typedef pair
        
          P; //first是最短距离，second是顶点编号 6 struct edge 7 { 8     int to,cost; 9     edge(int tt,int cc)10     {11         to=tt;12         cost=cc;13     }14 };15 const int maxn=5010;16 const int maxr=100010;17 int n,r;18 //图的邻接表表示19 vector
         
           G[maxr];20 int dist[maxn];21 int dist2[maxn];22 void solve()23 {24     //把每个顶点当前的最短距离用堆维护25     //每次从堆中取出的最小值就是下一次要使用的顶点26     //在每次更新时往堆里插入当前最短距离和顶点的值对27     //当取出的最小值不是最短距离的话，就丢弃这个值28     priority_queue
          
           
,greater
           
 > que;29 fill(dist,dist+n,INF);30 fill(dist2,dist2+n,INF);31 dist[0]=0;32 que.push(P(0,0));33 while(!que.empty())34 {35 P p=que.top();36 que.pop();37 int v=p.second,d=p.first;38 if(d>dist2[v]) continue;39 for(int i=0; i
            
             >n>>r;66 int from,to,cost;67 for(int i=0; i
             
              >from>>to>>cost;70 from--;71 to--;72 G[from].push_back(edge(to,cost));73 G[to].push_back(edge(from,cost));74 }75 solve();76 return 0;77 }