11235: 【原1235】Dijkstra

题目

题目描述

author: DS TA 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1235

Description

欢迎来到最后一题！

在做这一题之前，在我做古怪的事情之前，请先保证你对dijkstra算法（P382左右）以及优先队列堆（P158开始的内容）有充分的理解。

为了减少负担，3,6两题被浓缩成了一题。我们要用dijkstra算法实现求单源最短路径。我想你应该已经猜到了，你将遇到一些稀疏图（边数较少）而，图中结点个数n会很大（0<n<=10000），这导致朴素的dijkstra算法无法在规定的时间快速出解。所以你要用堆去优化它（请看P393,14.6的提示），使得每次获得具有最短路径的结点的时间复杂度由朴素算法的O（n）降到O（logn）。只有这样，你才能完成要求。给定无负权的有向图，起点start，终点end，请计算由start到end的最短路径（若存在多条最短路径，保留经过结点最少的那条）。

为简化题目，我们约定：用正整数1,2,3⋯⋯n来表示每个结点的ID（编号）

Input Format

第1行：n m start end //正整数n ，代表图中结点的数量。非负整数m代表要图中有向边的数量。

第2行到第1+m行: a b p //每行两个整数：代表结点a到结点b有一条有向边（a->b），权值为p

Output Format

第一行：一个整数，由start到end的最短路径上边的总权值的大小。

第二行：若干个整数，依次代表由起点到终点的最短路径上的结点，由空格分隔（若存在多条最短路径，输出经过结点最少的那条）

Sample Input

7 12 4 6
1 2 2
3 1 4
1 4 1
2 4 3
4 5 2
2 5 10
3 6 5
4 6 8
4 7 4 
5 7 6
7 6 1
4 3 2

Sample Output

5                      //P382的例子
4 7 6

Limits

0<n<=10000 0<=m<=200000

数据保证合法

两点之间可能有多条路径，也可能有自环

注：此题难度较大，若遇到问题，请及时与助教交流！

ligongzzz's solution

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

class type {
public:
    int val = 0;
    int pos = 0;
};

int dist[10009] = { 0 };
int position[10009] = { 0 };

class pqueue {
    type queue_data[10009];
    int _size = 0;
public:
    bool empty() {
        return _size == 0;
    }

    void push_up(int pos) {
        for (; pos > 1 && queue_data[pos].val < queue_data[pos >> 1].val; pos >>= 1) {
            swap(position[queue_data[pos].pos], position[queue_data[pos >> 1].pos]);
            swap(queue_data[pos], queue_data[pos >> 1]);
        }
    }

    void push_down(int pos) {
        for (pos <<= 1; pos <= _size; pos <<= 1) {
            if (pos < _size && queue_data[pos + 1].val < queue_data[pos].val)
                ++pos;
            if (queue_data[pos].val < queue_data[pos >> 1].val) {
                swap(position[queue_data[pos].pos], position[queue_data[pos >> 1].pos]);
                swap(queue_data[pos], queue_data[pos >> 1]);
            }
        }
    }

    int size() {
        return _size;
    }

    void push(int val, int pos) {
        ++_size;
        position[pos] = _size;
        queue_data[_size].val = val;
        queue_data[_size].pos = pos;
        push_up(_size);
    }

    type pop() {
        swap(position[queue_data[1].pos], position[queue_data[_size].pos]);
        swap(queue_data[1], queue_data[_size]);
        --_size;
        push_down(1);
        return queue_data[_size + 1];
    }

    void change(int val, int pos) {
        queue_data[position[pos]].val = val;
        push_up(position[pos]);
    }
};

int to[200009] = { 0 }, nxt[200009] = { 0 }, cost[200009] = { 0 };
int edge[10009] = { 0 }, edge_cnt = 0;
int total_num[10009] = { 0 }, pre[10009] = { 0 };
bool visited[10009] = { 0 };

void add(int u, int v, int c) {
    ++edge_cnt;
    nxt[edge_cnt] = edge[u];
    edge[u] = edge_cnt;
    to[edge_cnt] = v;
    cost[edge_cnt] = c;
}

pqueue queue_data;

int n, m, s, e;
int ans_data[10009] = { 0 };

int dijkstra(int a, int b) {
    int cur_pos = a;
    dist[cur_pos] = 0;
    total_num[cur_pos] = 1;
    visited[cur_pos] = true;
    while (true) {
        //先找到点来入队
        for (int p = edge[cur_pos]; p; p = nxt[p]) {
            if (!visited[to[p]]) {
                dist[to[p]] = dist[cur_pos] + cost[p];
                queue_data.push(dist[cur_pos] + cost[p], to[p]);
                total_num[to[p]] = total_num[cur_pos] + 1;
                pre[to[p]] = cur_pos;
                visited[to[p]] = true;
            }
            else if (dist[cur_pos] + cost[p] < dist[to[p]] ||
                (dist[cur_pos] + cost[p] == dist[to[p]] && total_num[cur_pos] + 1 < total_num[to[p]])) {
                dist[to[p]] = dist[cur_pos] + cost[p];
                queue_data.change(dist[cur_pos] + cost[p], to[p]);
                total_num[to[p]] = total_num[cur_pos] + 1;
                pre[to[p]] = cur_pos;
            }
        }
        //弹出
        if (queue_data.empty()) {
            return -1;
        }
        auto temp = queue_data.pop();
        if (temp.pos == b) {
            return dist[b];
        }
        cur_pos = temp.pos;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> s >> e;

    for (int i = 0; i < m; ++i) {
        int u, v, c;
        cin >> u >> v >> c;
        add(u, v, c);
    }

    cout << dijkstra(s, e) << "\n";
    for (int p = e, i = 0; p; p = pre[p], ++i)
        ans_data[i] = p;

    for (int i = total_num[e] - 1; i >= 0; --i)
        cout << ans_data[i] << " ";

    return 0;
}

Neight99's solution

#include <iostream>

using namespace std;

const int maxN = 1e5 + 100;
const int maxM = 2e6 + 100;
const int maxD = 1e9;

struct edgeNode {
    int data;
    int weight;
    edgeNode *next;

    edgeNode(int d = 0, int w = 0, edgeNode *n = 0)
        : data(d), weight(w), next(n) {}
};

struct verNode {
    int data;
    edgeNode *head;

    verNode(int d = 0, edgeNode *h = 0) : data(d), head(h) {}
};

struct queueNode {
    int dist;
    int node;

    bool operator<(const queueNode &right) const { return dist < right.dist; }
};

template <class Type>
class priorityQueue {
   private:
    int currentSize;
    Type *array;
    int maxSize;

    void doubleSpace();
    void buildHeap();
    void percolateDown(int);

   public:
    priorityQueue(int capacity = maxM);
    priorityQueue(const Type *data, int size);
    ~priorityQueue();
    bool isEmpty() const;
    void enQueue(const Type &x);
    Type deQueue();
    Type getHead() const;
};

template <class Type>
priorityQueue<Type>::priorityQueue(int capacity)
    : maxSize(capacity), currentSize(0) {
    array = new Type[capacity];
}

template <class Type>
priorityQueue<Type>::priorityQueue(const Type *data, int size)
    : maxSize(size + 10), currentSize(size) {
    array = new Type[maxSize];

    for (int i = 0; i < size; i++) {
        array[i + 1] = data[i];
    }

    buildHeap();
}

template <class Type>
priorityQueue<Type>::~priorityQueue() {
    delete[] array;
}

template <class Type>
bool priorityQueue<Type>::isEmpty() const {
    return currentSize == 0;
}

template <class Type>
Type priorityQueue<Type>::getHead() const {
    return array[1];
}

template <class Type>
void priorityQueue<Type>::enQueue(const Type &x) {
    // if (currentSize == maxSize - 1) {
    //     doubleSpace();
    // }

    int hole = ++currentSize;
    for (; hole > 1 && x < array[hole / 2]; hole /= 2) {
        array[hole] = array[hole / 2];
    }

    array[hole] = x;
}

template <class Type>
Type priorityQueue<Type>::deQueue() {
    Type minItem;

    minItem = array[1];
    array[1] = array[currentSize--];
    percolateDown(1);

    return minItem;
}

template <class Type>
void priorityQueue<Type>::percolateDown(int hole) {
    int child;
    Type tmp = array[hole];

    for (; hole * 2 <= currentSize; hole = child) {
        child = hole * 2;

        if (child != currentSize && array[child + 1] < array[child]) {
            child++;
        }

        if (array[child] < tmp) {
            array[hole] = array[child];
        } else {
            break;
        }
    }
    array[hole] = tmp;
}

template <class Type>
void priorityQueue<Type>::doubleSpace() {
    Type *tmp = array;

    maxSize *= 2;

    array = new Type[maxSize];
    for (int i = 0; i < currentSize; i++) {
        array[i] = tmp[i];
    }

    delete[] tmp;
}

template <class Type>
void priorityQueue<Type>::buildHeap() {
    for (int i = currentSize / 2; i > 0; i--) {
        percolateDown(i);
    }
}

int n, m, Start, End, sum = 0, minSum = 0, dis = 0;
int Distance[maxN], prev1[maxN], path[maxN], ansPath[maxN];
verNode *nodes[maxN];
bool known[maxN] = {0}, isVisited[maxN] = {0};

void Dijkstra(int);
void calPath(int, int, int *);
void DFS(int);

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> Start >> End;

    for (int i = 1; i <= n; i++) {
        nodes[i] = new verNode(i);
    }

    for (int i = 0; i < m; i++) {
        int temp1, temp2, temp3;
        cin >> temp1 >> temp2 >> temp3;
        nodes[temp1]->head = new edgeNode(temp2, temp3, nodes[temp1]->head);
    }

    Dijkstra(Start);
    dis = 0;
    calPath(Start, End, prev1);
    DFS(Start);

    if (dis > Distance[End]) {
        cout << dis << '\n';
    } else {
        cout << Distance[End] << '\n';
    }

    for (int i = 0; i < minSum; i++) {
        cout << ansPath[i] << ' ';
    }

    return 0;
}

void Dijkstra(int start) {
    int sNo;
    edgeNode *p;
    priorityQueue<queueNode> que;
    queueNode min, succ;

    for (int i = 1; i <= n; i++) {
        known[i] = 0;
        Distance[i] = maxD;
    }

    for (sNo = 1; sNo <= n; sNo++) {
        if (nodes[sNo]->data == start) {
            break;
        }
    }

    Distance[sNo] = 0;
    prev1[sNo] = sNo;
    min.dist = 0;
    min.node = sNo;
    que.enQueue(min);

    while (!que.isEmpty()) {
        min = que.deQueue();
        if (known[min.node]) {
            continue;
        } else {
            known[min.node] = 1;
            for (p = nodes[min.node]->head; p; p = p->next) {
                if (!known[p->data] &&
                    Distance[p->data] > min.dist + p->weight) {
                    succ.dist = Distance[p->data] = min.dist + p->weight;
                    prev1[p->data] = min.node;
                    succ.node = p->data;
                    que.enQueue(succ);
                }
            }
        }
    }
}

void calPath(int start, int end, int *prev1) {
    if (start == end) {
        ansPath[minSum++] = nodes[start]->data;
    } else {
        calPath(start, prev1[end], prev1);
        ansPath[minSum++] = nodes[end]->data;
    }
}

void DFS(int now) {
    path[sum++] = now;
    isVisited[now] = 1;

    if (now == End && sum < minSum && dis <= Distance[End]) {
        for (int i = 0; i < sum; i++) {
            ansPath[i] = path[i];
        }
        minSum = sum;
    } else if (now != End && sum < minSum && dis <= Distance[End]) {
        for (edgeNode *p = nodes[now]->head; p; p = p->next) {
            if (!isVisited[p->data]) {
                dis += p->weight;
                DFS(p->data);
                dis -= p->weight;
            }
        }
    }

    sum--;
    isVisited[now] = 0;
}

yyong119's solution

#include <iostream>
#include <queue>
#define INF 1 << 30
using namespace std;

const int MAX_N = 10010;
struct node{
    queue<int> p, c;
}a[MAX_N];
int n, m, startp, endp;
int dist[MAX_N], pre[MAX_N];
bool inque[MAX_N];

int main() {

    ios::sync_with_stdio(false);
    cin >> n >> m >> startp >> endp;
    for (int i = 1; i <= m; ++i) {
        int fromp, top, cost;
        cin >> fromp >> top >> cost;
        a[fromp].p.push(top);
        a[fromp].c.push(cost);
    }
    for (int i = 1; i <= n; ++i) {
        dist[i] = INF;
        pre[i] = i;
    }
    dist[startp] = 0;

    queue<int> que;
    que.push(startp); inque[startp] = true;
    while (!que.empty()) {
        int now = que.front();
        queue<int> tmpp = a[now].p, tmpc = a[now].c;
        while (!tmpp.empty()) {
            int nextp = tmpp.front(), nextc = tmpc.front();
            if (dist[nextp] > dist[now] + nextc) {
                dist[nextp] = dist[now] + nextc;
                pre[nextp] = now;
                if (!inque[nextp]) {
                    que.push(nextp);
                    inque[nextp] = true;
                }
            }
            tmpp.pop(); tmpc.pop();
        }
        que.pop(); inque[now] = false;
    }
    cout << dist[endp] << endl << startp;

    int line[MAX_N], t = 1;
    line[1] = endp;
    while (pre[line[t]] != startp) line[++t] = pre[line[t - 1]];
    for (int i = t; i > 0; --i) cout << " " << line[i];

    return 0;
}

Zsi-r's solution

#include <iostream>
#include <queue>

using namespace std;

struct sdNode //short distance node
{
    int end;
    int distance;
    int prev;
    int count;
    sdNode(){};
    sdNode(int e, int d, int p, int c) : end(e), distance(d), prev(p), count(c){};
};

class priorityQueue
{
public:
    priorityQueue(int capacity = 5);
    ~priorityQueue();
    bool isEmpty() const;
    void enQueue(int end, int distance, int prev, int count);
    sdNode deQueue();

private:
    int currentSize;
    sdNode *array; //array[0]不放东西
    int maxSize;

    void doubleSpace();
    void buildHeap(); //对一串数字进行有序化建堆
    void percolateDown(int hole);
};

priorityQueue::priorityQueue(int capacity)
{
    array = new sdNode[capacity];
    maxSize = capacity;
    currentSize = 0;
}

priorityQueue::~priorityQueue()
{
    delete[] array;
}

bool priorityQueue::isEmpty() const
{
    return currentSize == 0;
}

void priorityQueue::enQueue(int end, int distance, int prev, int count)
{
    if (currentSize == maxSize - 1) //因为array[0]不放东西
        doubleSpace();

    sdNode temp(end, distance, prev, count);
    //向上过滤
    int hole = ++currentSize;
    for (; hole > 1 && (distance < array[hole / 2].distance || (distance == array[hole / 2].distance && count < array[hole / 2].count)); hole /= 2)
        array[hole] = array[hole / 2];
    array[hole] = temp;
}

sdNode priorityQueue::deQueue()
{
    sdNode miniItem;
    miniItem = array[1];
    array[1] = array[currentSize--]; //把最大(maybe)的数放在第一个，再向下过滤
    percolateDown(1);
    return miniItem;
}

void priorityQueue::percolateDown(int hole) //向下过滤
{
    int child;
    sdNode tmp = array[hole];
    for (; hole * 2 <= currentSize; hole = child)
    {
        child = hole * 2;
        if (child != currentSize && (array[child + 1].distance < array[child].distance || (array[child + 1].distance == array[child].distance && array[child + 1].count < array[child].count))) //找小的儿子，如果child==currentSize，则没有右儿子
            child++;
        if (array[child].distance < tmp.distance || (array[child].distance == tmp.distance && array[child].count < tmp.count))
            array[hole] = array[child];
        else
            break;
    }
    array[hole] = tmp;
}

void priorityQueue::doubleSpace()
{
    sdNode *tmp = array;
    maxSize *= 2;
    array = new sdNode[maxSize];
    for (int i = 0; i <= currentSize; i++) //当currentSize == maxSize-1时，调用doubleSpace()
        array[i] = tmp[i];
    delete[] tmp;
}

class adjListGraph
{
public:
    adjListGraph(int vSize, const int d[]);
    void insert(int x, int y, int w);
    void dijkstra(int start, int end) const;
    ~adjListGraph();

private:
    struct edgeNode
    {
        int end;
        int weight;
        edgeNode *next;

        edgeNode(int e, int w, edgeNode *n = NULL)
        {
            end = e;
            weight = w;
            next = n;
        }
    };
    struct verNode
    {
        int ver;
        edgeNode *head;

        verNode(edgeNode *h = NULL) { head = h; }
    };

    int Vers, Edges;
    verNode *verList;

    void printPath(int start, int end, int prev[]) const;
};

adjListGraph::adjListGraph(int vSize, const int d[])
{
    this->Vers = vSize;

    verList = new verNode[vSize];
    for (int i = 0; i < vSize; i++)
    {
        verList[i].ver = d[i];
    }
}

adjListGraph::~adjListGraph()
{
    int i;
    edgeNode *p;

    for (i = 0; i < this->Vers; i++)
        while ((p = verList[i].head) != NULL)
        {
            verList[i].head = p->next;
            delete p;
        }
    delete[] verList;
}

void adjListGraph::insert(int x, int y, int w)
{
    int u = x - 1, v = y - 1;
    verList[u].head = new edgeNode(v, w, verList[u].head);
    ++this->Edges;
}

void adjListGraph::printPath(int start, int end, int prev[]) const
{
    if (start == end)
    {
        cout << verList[start].ver;
        return;
    }
    printPath(start, prev[end], prev);
    cout << ' ' << verList[end].ver;
}

void adjListGraph::dijkstra(int start, int end) const
{
    int *prev = new int[this->Vers];
    bool *known = new bool[this->Vers];

    int sNo, i, dis;
    edgeNode *p;
    sdNode temp;

    for (i = 0; i < this->Vers; i++)
    {
        known[i] = false;
    }

    sNo = start - 1;

    priorityQueue que;
    que.enQueue(sNo, 0, sNo, 1);
    prev[sNo] = sNo;

    while (!que.isEmpty())
    {
        temp = que.deQueue();

        if (known[temp.end])
            continue;

        known[temp.end] = true;
        prev[temp.end] = temp.prev;

        if (temp.end == end - 1)
            break;

        for (p = verList[temp.end].head; p != NULL; p = p->next)
            if (!known[p->end])
            {
                dis = temp.distance + p->weight;
                que.enQueue(p->end, dis, temp.end, temp.count+1);
            }
    }

    cout << temp.distance << endl;
    printPath(sNo, end - 1, prev);
}

int main()
{
    int n, m, start, end, edgestart, edgeend, edgeweight;

    cin >> n >> m >> start >> end;

    int *verarray = new int[n];
    for (int i = 0; i < n; i++)
    {
        verarray[i] = i + 1;
    }
    adjListGraph graph(n, verarray);
    for (int i = 0; i < m; i++)
    {
        cin >> edgestart >> edgeend >> edgeweight;
        graph.insert(edgestart, edgeend, edgeweight);
    }
    graph.dijkstra(start, end);
    return 0;
}