超时的Dij堆优化

URbit @ 2022-04-22 13:11:43

#include<iostream>
#include<queue>
using namespace std;

class edge
{
public:
    int cost;
    int VerAdj;
    edge* link;
    edge(int v, int w) :VerAdj(v), cost(w), link(nullptr) {}

};
class Vertex
{
public:
    int Ver;
    int dist;
    edge* adjecent;
    Vertex() :Ver(0), dist(INT32_MAX), adjecent(nullptr) {}

    bool operator<(const Vertex& rhs) const { return dist > rhs.dist; }
    bool operator>(const Vertex& rhs) const { return dist < rhs.dist; }
};
void Dijskra(Vertex* Head, const int& s, const int &n)
{
    int* path = new int[n + 1];
    int* visited = new int[n + 1];
    priority_queue<Vertex> Q;
    for (int i = 1; i <= n; i++)
    {
        path[i] = -1; Head[i].Ver = i;
        visited[i] = 0;
    }
    Q.push(Head[s]); 
    while (!Q.empty())
    {
        int u = Q.top().Ver;
        Q.pop();
        visited[u] = 1;
        for (edge* p = Head[u].adjecent; p; p = p->link)
        {
            int v = p->VerAdj;
            if (visited[v] == 0 && Head[u].dist + p->cost < Head[v].dist)
            {
                Head[v].dist = Head[u].dist + p->cost;
                path[v] = u; Q.push(Head[v]);
            }
        }
    }

    //打印
    for (int i = 1; i <= n; i++)
    {
        cout << Head[i].dist << ' ';
    }
}
int main()
{
    int n, m, s;
    int u, v, w;
    cin >> n >> m >> s;
    Vertex* Head = new Vertex[n + 1];

    for (int i = 1; i <= m; i++)
    {
        cin >> u >> v >> w;
        edge* temp = new edge(v, w);
        temp->link = Head[u].adjecent;
        Head[u].adjecent = temp;
    }
    Head[s].dist = 0;
    Dijskra(Head, s, n);
}

by happybob @ 2022-04-22 13:44:28

@URbit

#include<iostream>
#include<queue>
using namespace std;

class edge
{
public:
    int cost;
    int VerAdj;
    edge* link;
    edge(int v, int w) :VerAdj(v), cost(w), link(nullptr) {}

};
class Vertex
{
public:
    int Ver;
    int dist;
    edge* adjecent;
    Vertex() :Ver(0), dist(INT32_MAX), adjecent(nullptr) {}

    bool operator<(const Vertex& rhs) const { return dist > rhs.dist; }
    bool operator>(const Vertex& rhs) const { return dist < rhs.dist; }
};
void Dijskra(Vertex* Head, const int& s, const int &n)
{
    int* path = new int[n + 1];
    int* visited = new int[n + 1];
    priority_queue<Vertex> Q;
    for (int i = 1; i <= n; i++)
    {
        path[i] = -1; Head[i].Ver = i;
        visited[i] = 0;
    }
    Q.push(Head[s]); 
    while (!Q.empty())
    {
        int u = Q.top().Ver;
        Q.pop();
        if (visited[u]) continue; // 这里
        visited[u] = 1;
        for (edge* p = Head[u].adjecent; p; p = p->link)
        {
            int v = p->VerAdj;
            if (visited[v] == 0 && Head[u].dist + p->cost < Head[v].dist)
            {
                Head[v].dist = Head[u].dist + p->cost;
                path[v] = u; Q.push(Head[v]);
            }
        }
    }

    //打印
    for (int i = 1; i <= n; i++)
    {
        cout << Head[i].dist << ' ';
    }
}
int main()
{
    int n, m, s;
    int u, v, w;
    cin >> n >> m >> s;
    Vertex* Head = new Vertex[n + 1];

    for (int i = 1; i <= m; i++)
    {
        cin >> u >> v >> w;
        edge* temp = new edge(v, w);
        temp->link = Head[u].adjecent;
        Head[u].adjecent = temp;
    }
    Head[s].dist = 0;
    Dijskra(Head, s, n);
}

by URbit @ 2022-04-24 19:53:50

多谢大佬