Find a lot of forgotten, look again.

Found a simple most short circuit board sub-test code :POJ 2387

Regular Dijkstra

Dijkstra algorithm (Dijkstra) was put forward by Dutch computer scientist Dijkstra in 1959, so it is also called Dijkstra algorithm. The shortest path algorithm from one vertex to other vertices is used to solve the shortest path problem in power graph. The main characteristic of Dijkstra algorithm is that it starts from the starting point and adopts the strategy of greedy algorithm to traverse to the adjacent nodes of the nearest and unvisited vertex at the beginning point each time until it extends to the end point.

O(n2) O(n^2) O(n^2) O(n^2).

Code:

ll mp[1010] [1010];
ll dis[1010], vis[1010];

int main(a)
{
    fill(mp[0], mp[0] + 1010 * 1010, INF);
    for (int i = 1; i <= 1000; i++)
        mp[i][i] = 0;
    ll t, n;
    cin >> t >> n;
    while (t--)
    {
        ll u, v, w;
        cin >> u >> v >> w;
        mp[u][v] = mp[v][u] = min(mp[u][v], w);
    }
    fill(dis, dis + 1010, INF);
    dis[1] = 0;
    for (int i = 1; i <= n; i++)
    {
        ll minn = INF, v = - 1;
        for (int j = 1; j <= n; j++) // Find the nearest unused point v to the starting point each time to update
        {
            if (dis[j] < minn && !vis[j])
            {
                minn = dis[j];
                v = j;
            }
        }
        if (v == - 1)
            break;
        vis[v] = 1;
        for (int j = 1; j <= n; j++) // Update the other points with the found point v
            if (dis[j] > dis[v] + mp[v][j])
                dis[j] = dis[v] + mp[v][j];
    }
    cout << dis[n] << endl;
}
Copy the code

Heap optimization dijkstra

The time complexity of the normal dijkstra is O(n2) O(n^2) O(n2). We can use a small top heap O(1) O(1) O(1) O(1) take the nearest point V, the time complexity of the insertion point is O(L O gn) O(logn) O(logn) optimization 2: Relaxation doesn’t have to go through all the points, it just has to find the points that are connected to v, so it can be optimized using adjacency lists or linked forward stars

So far, the dijkstra time complexity of heap optimization + chain forward star optimization is O(m L O gn) O(mlogn) O(mlogn), where M is the number of edges and n is the number of vertices.

Code:

ll dis[1010];
ll head[1010];

struct node
{
    ll v, w, next;
} e[10010];
ll ct = 1;

void add(ll u, ll v, ll w)
{
    e[ct].v = v;
    e[ct].w = w;
    e[ct].next = head[u];
    head[u] = ct++;
}
priority_queue<pll> q;
ll vis[1010];

void dij(ll s)
{
    fill(dis, dis + 1010, INF);
    dis[s] = 0;
    q.push(make_pair(0.1));
    while (q.size())
    {
        ll u = q.top().second; //O1 takes the nearest point to the starting point
        q.pop(a);if (vis[u])
            continue;
        vis[u] = 1;
        for (int i = head[u]; i; i = e[i].next)
        {
            ll w = e[i].w;
            ll v = e[i].v;
            if (dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
                q.push(make_pair(-dis[v], v)); }}}}int main(a)
{
    int t, n;
    cin >> t >> n;
    while (t--)
    {
        ll u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
        add(v, u, w);
    }
    dij(1);
    cout << dis[n] << endl;
    return 0;
}
Copy the code