# Dijkstra算法(Dijkstra algorithm)-其他

## Dijkstra算法(Dijkstra algorithm)

### 代码：

``````#include <bits/stdc++.h>
using namespace std;

const int N = 510;
int n, m;
int g[N][N];
int dist[N];
bool st[N];

int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;

for (int i = 1; i <= n; i++)
{
int t = -1;
for (int j = 1; j <= n; j++)
if (!st[j] && (t == -1 || dist[j] < dist[t]))
t = j;

for (int j = 1; j <= n; j++)
dist[j] = min(dist[j], dist[t] + g[t][j]);

st[t] = true;
}
if (dist[n] == 0x3f3f3f3f)
return -1;
else
return dist[n];
}

int main()
{
cin >> n >> m;
memset(g, 0x3f, sizeof g);

while (m--)
{
int a, b, c;
cin >> a >> b >> c;
g[a][b] = min(g[a][b], c);
}

cout << dijkstra();
return 0;
}
``````

### 代码：

``````#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int>PII;

const int N = 1e6 + 10;
int n, m;
int h[N], e[N], ne[N], w[N], idx;
int dist[N];
bool st[N];

void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;

priority_queue<PII, vector<PII>, greater<PII>>heap;
heap.push({ 0,1 });

while (heap.size())
{
auto t = heap.top();
heap.pop();

int ver = t.second;
int distance = t.first;

if (st[ver])
continue;
st[ver] = true;

for (int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
int m = w[i];
if (dist[j] > dist[ver] + m)
{
dist[j] = dist[ver] + m;
heap.push({ dist[j], j });
}
}
}

if (dist[n] == 0x3f3f3f3f)
return -1;
else
return dist[n];
}

int main()
{
memset(h, -1, sizeof h);

cin >> n >> m;
while (m--)
{
int a, b, c;
cin >> a >> b >> c;
}

cout << dijkstra();
return 0;
}
``````
————————

### code:

``````#include <bits/stdc++.h>
using namespace std;

const int N = 510;
int n, m;
int g[N][N];
int dist[N];
bool st[N];

int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;

for (int i = 1; i <= n; i++)
{
int t = -1;
for (int j = 1; j <= n; j++)
if (!st[j] && (t == -1 || dist[j] < dist[t]))
t = j;

for (int j = 1; j <= n; j++)
dist[j] = min(dist[j], dist[t] + g[t][j]);

st[t] = true;
}
if (dist[n] == 0x3f3f3f3f)
return -1;
else
return dist[n];
}

int main()
{
cin >> n >> m;
memset(g, 0x3f, sizeof g);

while (m--)
{
int a, b, c;
cin >> a >> b >> c;
g[a][b] = min(g[a][b], c);
}

cout << dijkstra();
return 0;
}
``````

### code:

``````#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int>PII;

const int N = 1e6 + 10;
int n, m;
int h[N], e[N], ne[N], w[N], idx;
int dist[N];
bool st[N];

void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;

priority_queue<PII, vector<PII>, greater<PII>>heap;
heap.push({ 0,1 });

while (heap.size())
{
auto t = heap.top();
heap.pop();

int ver = t.second;
int distance = t.first;

if (st[ver])
continue;
st[ver] = true;

for (int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
int m = w[i];
if (dist[j] > dist[ver] + m)
{
dist[j] = dist[ver] + m;
heap.push({ dist[j], j });
}
}
}

if (dist[n] == 0x3f3f3f3f)
return -1;
else
return dist[n];
}

int main()
{
memset(h, -1, sizeof h);

cin >> n >> m;
while (m--)
{
int a, b, c;
cin >> a >> b >> c;