# 11235: 【原1235】Dijkstra

### 题目描述

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

## 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;
}

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;

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();
};

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;
}

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;
}

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

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;

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

int Vers, Edges;
verNode *verList;

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

{
this->Vers = vSize;

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

{
int i;
edgeNode *p;

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

void adjListGraph::insert(int x, int y, int w)
{
int u = x - 1, v = y - 1;
++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;
}