题目描述
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。
请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。
输入描述
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出描述
输出一个整数，表示 1 号点到 n 号点的最短距离。
如果路径不存在，则输出 −1。
朴素版：
1≤n≤500,
1≤m≤105,
图中涉及边长均不超过10000。
优化版：
1≤n,m≤1.5×105,
图中涉及边长均不小于 0，且不超过 10000。
示例
输入
3 3
1 2 2
2 3 1
1 3 4输出
3
Dijkstra算法
Dijkstra算法是经典的解决无负权边单源最短路问题的算法，按照路径长度递增的次序产生最短路径。
该算法非常经典，具体算法过程不再细述，下面给出算法的核心及其证明。
我们设图G的顶点集合为V，再设一个集合S表示已求得最短路径的终点的集合（S怎么来的下面再说）。
设下一条最短路径（终点为x），那么它只能是弧（v，x）或者只通过S中的顶点到达x即（v，vi,….,x）。我们来证明一下：
假设（v，…,x）路径上有一个顶点不在S中，则说明存在一条终点不在S中而长度比此路径还短的路径。但这是不可能的。因为我们按长度递增的顺序来产生各最短路径，所以长度比此路径还短的所有路径均已产生，他们的终点一定在S中。
另外，如果要求到达某个点的最短路径的数量，可以在找到当前距离最近点后更新其它点距离时做记录，更新后如果等于原来的说明存在一条新的最短路径。
堆优化
算法中有一步是从未在S中的点当中选出到起点路径长度最短的一个点。对于这一步，我们可以通过一个小根堆来实现优化，大大降低这一步的时间复杂度。
朴素版代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=501;
int n,m;
int dist[N];
int g[N][N];
bool st[N];
int dijkstra()
{
memset(dist,0x3f,sizeof(dist));
dist[1]=0;
for(int i=0;i<n;i++)
{
int t=-1;
for(int j=1;j<=n;j++)
{
if(!st[j] && (t==-1 || dist[t]>dist[j]))
t=j;
}
st[t]=true;
for(int j=1;j<=n;j++)
dist[j]=min(dist[j],dist[t]+g[t][j]);
}
return dist[n]==0x3f3f3f3f? -1:dist[n];
}
int main()
{
memset(g,0x3f,sizeof(g));
cin >> n >> m;
for(int i=0;i<m;i++)
{
int a,b,c;
cin >> a >> b >> c;
g[a][b]=min(g[a][b],c);
}
cout << dijkstra() << endl;
return 0;
}堆优化代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <functional>
using namespace std;
typedef pair<int, int> P;
const int N = 1.5e5 + 10;
int n, m;
int dist[N];
int h[N], e[N], ne[N], w[N], idx;
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<P, vector<P>, greater<P>> heap;
heap.push(make_pair(0, 1));
while (!heap.empty())
{
P t = heap.top();
heap.pop();
int d = t.first, v = t.second;
if (st[v]) //一个点可能被多次更新从而多次入堆
continue; //第一次出堆为最优解
//加以标记 可节省时间
st[v] = true;
for (int i = h[v]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > w[i] + d)
{
dist[j] = w[i] + d;
heap.push(make_pair(dist[j], j));
}
}
}
return dist[n] == 0x3f3f3f3f ? -1 : dist[n];
}
int main()
{
memset(h, -1, sizeof(h));
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
cout << dijkstra() << endl;
return 0;
}
