杂好题汇总

1、hdu 6705 path

题意：有向图求第k大路径（权值和），每条边可以走无数次。

分析：因为k很小，所以应该是预处理出前k大路径，首先想到的是贪心，大致想法是用一个优先队列弹出前k个，无奈后面没想明白，看了题解才恍然大悟。首先把每个点出边按权值排序，每个点权值最小的出边最有可能是前k大，n个点中出边最小的一定是最小的，确定完之后还要考虑这个点和其他点组成路径，要保证最小，只能和这条边的出点的权值最小的出边相连，还有一种情况，就是从起点走后一大的边到达出点，有点绕，画个图就很容易理解了。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 5e4+5;
int t,n,m,q,qu[N],ans[N],qmx;
vector<pair<int,int> > g[N];

struct nd {
    int u,len,id;
    bool operator < (const nd &b) const {
        return len > b.len;
    }
};

void bfs() {
    priority_queue<nd> pq;
    for(int i=1;i<=n;i++)
        if(g[i].size()) pq.push({i,g[i][0].first,0});
    int cnt=0;
    while(!pq.empty()) {
        nd tp = pq.top();
        pq.pop();
        ans[++cnt] = tp.len;
        if(cnt == qmx) break;
        if(tp.id + 1 < g[tp.u].size())
            pq.push({tp.u, tp.len-g[tp.u][tp.id].first+g[tp.u][tp.id+1].first, tp.id+1});
        int v = g[tp.u][tp.id].second;
        if(g[v].size())
            pq.push({v, tp.len+g[v][0].first, 0});
    }
    for(int i=1;i<=q;i++) printf("%d\n",ans[qu[i]]);
}

int main(){
    scanf("%d",&t);
    while(t--) {
        qmx = 0;
        scanf("%d%d%d",&n,&m,&q);
        for(int i=1;i<=m;i++) {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            g[u].push_back({w,v});
        }
        for(int i=1;i<=n;i++)
            sort(g[i].begin(),g[i].end());
        for(int i=1;i<=q;i++)
            scanf("%d",&qu[i]),qmx=max(qmx,qu[i]);
        bfs();
        for(int i=1;i<=n;i++) g[i].clear();
    }
	return 0;
}