1
2
3
4

for (int k = 0; k < nodeCount; k++)
    for (int i = 0; i < nodeCount; i++)
        for (int j = 0; j < nodeCount; j++)
            DP[i][j] = min(DP[i][j], DP[i][k]+ DP[k][j]);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class cmp {
    public:
        bool operator()(edge a,edge b)
        {
            if(a.weight<b.weight)
                return true;
            return false;
        }
};

dis[a] = 0;
priority_queue<edge, vector<edge>, cmp> pq;
pq.push({a, 0});
while (!pq.empty()) {
    edge u = pq.top();

    pq.pop();
    if (!vis[u.to_node]) {
        vis[u.to_node] = 1;
        for (auto i : mp[u.to_node]) {
            if (dis[i.to_node] > dis[u.to_node] + i.weight) {
                dis[i.to_node] = dis[u.to_node] + i.weight;
                pq.push({i.to_node, dis[i.to_node]});
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

void dfs(int u) {
    if (!vis[u]) {
        vis[u] = true;
        for (auto j : edge[u]) dfs(j);
        toposort.push_back(u);
    }
}

for (int i = 1; i <= n; i++) dfs(i);
reverse(toposort.begin(), toposort.end());