[FJOI2014]最短路径树问题

题目描述

给一个包含\(n\)个点，\(m\)条边的无向连通图。从顶点\(1\)出发，往其余所有点分别走一次并返回。

往某一个点走时，选择总长度最短的路径走。若有多条长度最短的路径，则选择经过的顶点序列字典序最小的那条路径(如路径\(A\)为\(1,32,11\)，路径\(B\)为\(1,3,2,11\)，路径\(B\)字典序较小。注意是序列的字典序的最小，而非路径中节点编号相连的字符串字典序最小)。到达该点后按原路返回，然后往其他点走，直到所有点都走过。

可以知道，经过的边会构成一棵最短路径树。请问，在这棵最短路径树上，最长的包含\(K\)个点的简单路径长度为多长？长度为该最长长度的不同路径有多少条？

这里的简单路径是指：对于一个点最多只经过一次的路径。不同路径是指路径两端端点至少有一个不同，点\(A\)到点\(B\)的路径和点\(B\)到点\(A\)视为同一条路径。

输入输出格式

输入格式：

第一行输入三个正整数\(n\),\(m\),\(K\)，表示有\(n\)个点\(m\)条边，要求的路径需要经过\(K\)个点。

接下来输入\(m\)行，每行三个正整数\(A_i,B_i,C_i(1\le A_i,B_i\le n,1 \le C_i\le10000)\)，表示\(A_i\)和\(B_i\)间有一条长度为\(C_i\)的边。

数据保证输入的是连通的无向图。

输出格式：

输出一行两个整数，以一个空格隔开，第一个整数表示包含\(K\)个点的路径最长为多长，第二个整数表示这样的不同的最长路径有多少条。

说明

对于所有数据\(n\le30000,m\le60000\)，\(2\le K\le n\)。

数据保证最短路径树上至少存在一条长度为K的路径。

---

Solution

第二自然段的题意我现在都没弄懂。

用我的理解就是先保证最短路，然后保证连边的编号的字典序是最小的。

这个可以先把最短路图跑出来，然后对每个点的出边排序，从\(1\)开始跑\(DFS\)，边跑边连边。

然后就是淀粉质了。

吐槽题意+强行拼题+写起来不爽（不是为了了解一下最短路树我才不写呢）

复杂度\(O(nlogn)\)

---

Code:

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         const int N=3e4+10;struct Edge{    int v,w;    bool friend operator <(Edge n1,Edge n2){return n1.v
         
          
            e[N],e0[N];int n,m,k;const int inf=0x3f3f3f3f;#define P std::pair 
           
            std::priority_queue 
            
             
,std::greater 
             
 > q;int dis[N],used[N];int head[N],to[N<<1],edge[N<<1],Next[N<<1],cnt;void add(int u,int v,int w){ to[++cnt]=v,Next[cnt]=head[u],edge[cnt]=w,head[u]=cnt;}void disj(){ memset(dis,0x3f,sizeof(dis)); q.push(std::make_pair(dis[1]=0,1)); while(!q.empty()) { int u=q.top().second; q.pop(); if(used[u]) continue; used[u]=1; for(int i=0;i
              
               dis[u]+w) { dis[v]=dis[u]+w; q.push(std::make_pair(dis[v],v)); } } } memset(used,0,sizeof(used));}void dfsbuild(int now){ used[now]=1; for(int i=0;i
               
                y?x:y;}void dfsroot(int now,int fa,int sz){ siz[now]=1; int mx0=0; for(int i=head[now];i;i=Next[i]) { int v=to[i]; if(v==fa||del[v]) continue; dfsroot(v,now,sz); mx0=max(mx0,siz[v]); siz[now]+=siz[v]; } mx0=max(mx0,sz-siz[now]); if(mx0
                
                 k) return; if(mx
                 
                  mxlen[j]) { scnt[j]=tcnt[j]; mxlen[j]=tmxlen[j]; } else if(tmxlen[j]==mxlen[j]) scnt[j]+=tcnt[j]; tcnt[j]=0,tmxlen[j]=-inf; } } if(mx
                 
                
               
              
            
           
          
         
        
       
      
     
    

---

2018.10.22