带权的DAG节点排序

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;

class Vertex {
    int lable; //标号
    int weight; //权值
    int in; //入度
    ArrayList<Vertex> connectList; //该顶点所指向的点
    Vertex(int lable, int weight) {
        this.lable = lable;
        this.weight = weight;
        this.connectList = new ArrayList<Vertex>();
    }
}

/**
 * 拓扑排序
 * 
 * @author wylu
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strs = br.readLine().split(" ");
        int n = Integer.parseInt(strs[0]), e = Integer.parseInt(strs[1]);

        //建图
        HashMap<Integer, Vertex> dag = new HashMap<Integer, Vertex>();
        for (int i = 0; i < n; i++) {
            strs = br.readLine().split(" ");
            int lable = Integer.parseInt(strs[0]), weight = Integer.parseInt(strs[1]);
            dag.put(lable, new Vertex(lable, weight));
        }
        for (int i = 0; i < e; i++) {
            strs = br.readLine().split(" ");
            int from = Integer.parseInt(strs[0]), to = Integer.parseInt(strs[1]);
            dag.get(from).connectList.add(dag.get(to));
            dag.get(to).in++;
        }

        ArrayList<Integer> res = topologicalSort(dag);
        for (int i = 0; i < res.size() - 1; i++) {
            System.out.print(res.get(i) + " ");
        }
        System.out.println(res.get(res.size() - 1));
    }

    private static ArrayList<Integer> topologicalSort(HashMap<Integer, Vertex> dag) {
        ArrayList<Integer> res = new ArrayList<>();

        //大顶堆
        PriorityQueue<Vertex> queue = new PriorityQueue<>(new Comparator<Vertex>() {
            @Override
            public int compare(Vertex o1, Vertex o2) {
                return -Integer.compare(o1.weight, o2.weight);
            }
        });

        //入度为0的点入队
        for (Integer lable : dag.keySet()) {
            if (dag.get(lable).in == 0) queue.offer(dag.get(lable));
        }

        while (!queue.isEmpty()) {
            Vertex fromV = queue.poll();
            res.add(fromV.lable);

            for (Vertex toV : dag.get(fromV.lable).connectList) {
                toV.in--; //邻接点入度减1
                if (toV.in == 0) queue.offer(toV);
            }
        }
        return res;
    }
}

#include <bits/stdc++.h>
using namespace std;

struct P{
    int u, w;
    friend bool operator > (P p1, P p2){
        return p1.w < p2.w;
    }
};

int main(){
    int n, m, u, v, w;
    scanf("%d%d", &n, &m);
    vector<P> node(n+1);
    vector<int> d(n+1, 0);
    vector<bool> vis(n+1, false);
    vector<int> edge[n+1];
    vector<int> r;
    for(int i=0;i<n;i++){
        scanf("%d%d", &u, &w);
        node[i+1] = {u, w};
    }
    for(int i=0;i<m;i++){
        scanf("%d%d", &u, &v);
        edge[u].push_back(v);
        d[v]++;
    }
    priority_queue<P, vector<P>, greater<P> > q;
    for(int i=1;i<=n;i++)
        if(d[i] == 0){
            q.push(node[i]);
            vis[i] = true;
        }
    while(!q.empty()){
        int t = q.size();
        while(t--){
            P p = q.top();
            q.pop();
            u = p.u;
            w = p.w;
            for(auto &v: edge[u])
                d[v]--;
            r.push_back(u);
        }
        for(int i=1;i<=n;i++)
            if(d[i]==0 && !vis[i]){
                q.push(node[i]);
                vis[i] = true;
            }
    }
    for(int i=0;i<n;i++)
        printf("%d ", r[i]);
    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int main(void) {
  int n, e;
  cin >> n >> e;
  vector<int> weights(n + 1);
  
  int seq, w;
  for (int i = 0; i < n; ++i) {
    cin >> seq >> w;
    weights[seq] = w;
  }
  
  int u, v;
  vector<vector<int>> g(n + 1);
  vector<int> indegrees(n + 1, 0);
  for (int i = 0; i < e; ++i) {
    cin >> u >> v;
    g[u].emplace_back(v);
    ++indegrees[v];
  }
  
  priority_queue<pair<int, int>> q; // maximum heap
  for (int u = 1; u <= n; ++u) 
    if (!indegrees[u]) q.emplace(weights[u], u);
  
  while (not q.empty()) {
    const auto [weight, curr] = q.top(); q.pop();
    cout << curr << ' ';
    for (const int nxt : g[curr])
      if (!--indegrees[nxt]) q.emplace(weights[nxt], nxt);
  }
  
  return 0;
}