04

http://acm.hdu.edu.cn/showproblem.php?pid=6705

分析；先把每条边以 形式放进堆，堆按路径权值从小到大排序，然后每次取出堆顶，用v的出边扩展 新的路径。但是一个点的出度可能会非常大（如菊花图），可以发现，将出边排序之后，

每次只需要扩 展当前点最小的出边，和扩展到当前点的边的下一条边即可。堆中需要记录当前结点，当前距离，上一 节点距离，扩展到当前节点时下一条应该扩展的边。

（注意，如果一次性扩展当前点连出去的所有权值 相同的边，是会TLE的，实际上也是没有必要的。）

复杂度：O（k*log（m+k））

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;typedef long long ll;#define pb push_backconst int M=1e5+5;struct node{    ll cost;    int u,id;    node(ll costt=0,int uu=0,int idd=0 ){        cost=costt;        u=uu;        id=idd;    }    bool operator < ( const node &b)const{        return cost>b.cost;    }};#define pli pair
           
            vector
            
              e[M];ll ans[M];int a[M];priority_queue
             
               que;int main(){ int t; scanf("%d",&t); while(t--){ int n,m,q; scanf("%d%d%d",&n,&m,&q); for(int i=0;i<=n;i++) e[i].clear(); while(!que.empty()) que.pop(); for(int i=1;i<=m;i++){ int u,v; ll w; scanf("%d%d%lld",&u,&v,&w); e[u].pb(pli(w,v)); } int maxxk=0; for(int i=1;i<=q;i++){ scanf("%d",&a[i]); maxxk=max(maxxk,a[i]); } for(int i=1;i<=n;i++) sort(e[i].begin(),e[i].end()); for(int i=1;i<=n;i++) if(e[i].size()) que.push(node(e[i][0].first,i,0)); int tot=0; while(!que.empty()){ node now=que.top(); que.pop(); int u=now.u; int id=now.id; ll Cost=now.cost; if(Cost) ans[++tot]=Cost; if(tot==maxxk) break; if(id<(int)e[u].size()-1) que.push(node(Cost-e[u][id].first+e[u][id+1].first,u,id+1)); int v=e[u][id].second; if(e[v].size()) que.push(node(Cost+e[v][0].first,v,0)); } for(int i=1;i<=q;i++) printf("%lld\n",ans[a[i]]); } return 0;}