题意：求无起止点的 k 短路
多组数据，效率约为nlogn
解法：
由于无起止点，就可以用类似kruskal的贪心思路，优先考虑最短的道路并计数。
每使用一个当前最短道路，就入队一个次短道路。这样可以保证空间是合法的，并且能维护正确答案。
尝试拓展更多一段的道路。入优先队列。
维护答案。
代码：
1 #include<bits/stdc++.h>
2 #define ll long long
3 using namespace std;
4 const int maxn=5e4+10;
5 int n,m,q,edge_head[maxn],num_edge,Q[maxn];
6 ll ans[maxn];
7 struct Edge{
8 ll sum;
9 int u,v,id;
10 bool operator < (const Edge&a)const{
11 return a.sum<sum;
12 }
13 }ed;
14 struct Edge2{
15 int to,nx;ll dis;
16 }edge[maxn];
17 priority_queue<Edge>pri;
18 /*void add_edge(int from,int to,ll dis){
19 edge[++num_edge].nx=edge_head[from];
20 edge[num_edge].to=to;
21 edge[num_edge].dis=dis;
22 edge_head[from]=num_edge;
23 return;
24 }*/
25 vector<pair<int,int> >mp[maxn];
26 int main(){
27 int T;cin>>T;
28 while(T--){
29 while(!pri.empty())pri.pop();
30 // memset(edge_head,0,sizeof(edge_head));
31 // num_edge=0;
32 scanf("%d%d%d",&n,&m,&q);
33 for(int i=1;i<=n;i++)mp[i].clear();
34 for(int i=1;i<=m;i++){
35 int u,v;ll w;
36 scanf("%d%d%lld",&u,&v,&w);
37 // add_edge(u,v,w);
38 mp[u].push_back(make_pair(w,v));
39 }
40 for(int i=1;i<=n;i++)
41 sort(mp[i].begin(),mp[i].end());
42 for(int i=1;i<=n;i++)
43 if(mp[i].size()){
44 ed.id=0;
45 ed.u=i;
46 ed.v=mp[i][0].second;
47 ed.sum=mp[i][0].first;
48 pri.push(ed);
49 }
50 int mxq=0;
51 for(int i=1;i<=q;i++){
52 scanf("%d",&Q[i]);
53 if(Q[i]>mxq)mxq=Q[i];
54 }
55 int cnt=0;
56 while(!pri.empty()){
57 ed=pri.top();
58 ans[++cnt]=ed.sum;
59 if(cnt==mxq)break;
60 pri.pop();
61 int id=ed.id;
62 if(id+1<(int)mp[ed.u].size()){
63 Edge ed2;
64 ed2.id=id+1;
65 ed2.sum=ans[cnt]-mp[ed.u][id].first+mp[ed.u][id+1].first;
66 ed2.u=ed.u;
67 ed2.v=mp[ed.u][id+1].second;
68 pri.push(ed2);
69 // if(ed2.sum==4)printf("!%d %d\n",ed2.u,ed2.v);
70 }
71 if(mp[ed.v].size()){
72 Edge ed2;
73 ed2.id=0;
74 ed2.sum=ans[cnt]+mp[ed.v][0].first;
75 ed2.v=mp[ed.v][0].second;
76 ed2.u=ed.v;
77 pri.push(ed2);
78 // if(ed2.sum==4)printf("!%d %d\n",ed2.u,ed2.v);
79 }
80 }
81 for(int i=1;i<=q;i++)printf("%lld\n",ans[Q[i]]);
82 }
83 return 0;
84 }
View Code
By:AlenaNuna
标签：head,num,int,pri,edge,2019CCPC,vector,maxn,path From： https://www.cnblogs.com/AlenaNuna/p/16656315.html