一：朴素算法
给定一个n个点m条边的有向图，图中可能存在重边和自环，所有边权均为正值。
请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出-1。
输入格式
第一行包含整数n和m。
接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。
输出格式
输出一个整数，表示1号点到n号点的最短距离。
如果路径不存在，则输出-1。
数据范围
1≤n≤5001≤n≤500,
1≤m≤1051≤m≤105,
图中涉及边长均不超过10000。
输入样例：
3 3
1 2 2
2 3 1
1 3 4
输出样例：
3
#############################################################
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 //本题 顶点数n比边数m小很多，所以属于稠密图，稠密图用邻接矩阵存储，稀疏图用邻接表存 5 const int N = 510; 6 7 vector<vector<int> > g(N,vector<int>(N, 0x3f3f3f3f)); 8 vector<int> d(N, 0x3f3f3f3f);//表示每个点到起点的最短距离 9 vector<bool> f(N, false);//表示每个点到起点的距离是否是最短的 10 int n, m; 11 //返回从1号点到n号点的最短距离 12 int dijkstra(){ 13 d[1] = 0; 14 //进行n次迭代，每次能确定一个到起点的最小值 15 for(int i = 1;i <= n;++i){ 16 //在d数组里面找到未确定是最小的最小的那个，就是距离起点最小的，这个数学可以证明 17 int t = -1; 18 for(int j = 1;j <= n;++j) 19 if(!f[j] && (t == -1 || d[t] > d[j])) t = j; 20 if(t != -1){ 21 //标记是最小的 22 f[t] = true; 23 //用这个最小的去更新d数组 24 for(int j = 1;j <= n;++j) d[j] = min(d[j], d[t] + g[t][j]); 25 } 26 } 27 return d[n]; 28 } 29 int main(){ 30 cin >> n >> m; 31 while(m--){ 32 int x,y,z; 33 cin >> x >> y >> z; 34 g[x][y] = min(g[x][y], z); 35 } 36 int t = dijkstra(); 37 if(t == 0x3f3f3f3f)cout << -1 << endl; 38 else cout << t << endl; 39 return 0; 40 }
二： 加堆优化：
给定一个n个点m条边的有向图，图中可能存在重边和自环，所有边权均为非负值。
请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出-1。
输入格式
第一行包含整数n和m。
接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。
输出格式
输出一个整数，表示1号点到n号点的最短距离。
如果路径不存在，则输出-1。
数据范围
1≤n,m≤1051≤n,m≤105,
图中涉及边长均不小于0，且不超过10000。
输入样例：
3 3
1 2 2
2 3 1
1 3 4
输出样例：
3
############################################################
1 #include <bits/stdc++.h> 2 using namespace std; 3 //本题属于稀疏图，所以用邻接表 4 const int N = 1e5+10; 5 typedef pair<int, int> pii;//使用pair的first记录距离， second记录对应的顶点 6 7 vector<int> h(N,-1), e(N,0), w(N,0), ne(N, 0); 8 int idx; 9 vector<int> dist(N,0x3f3f3f3f); 10 vector<bool> f(N, false); 11 int n, m; 12 13 void add(int a, int b, int c){ 14 e[idx] = b; 15 w[idx] = c; 16 ne[idx] = h[a]; 17 h[a] = idx++; 18 } 19 20 int dijkstra(){ 21 priority_queue<pii, vector<pii>, greater<pii> > pq;//小根堆 22 dist[1] = 0; 23 pq.push({0, 1}); 24 while(!pq.empty()){ 25 auto t = pq.top(); pq.pop(); 26 int d = t.first, v = t.second; 27 if(f[v])continue; 28 f[v] = true; 29 for(int i = h[v];i != -1;i = ne[i]){ 30 int j = e[i]; 31 if(dist[j] > d + w[i]){ 32 dist[j] = d + w[i]; 33 pq.push({dist[j],j});//最小的元素只能产生在更新的元素中 34 } 35 } 36 } 37 return dist[n] == 0x3f3f3f3f ? -1 : dist[n]; 38 } 39 40 int main(){ 41 cin >> n >> m; 42 while(m--){ 43 int x, y, z; 44 cin >> x >> y >> z; 45 add(x, y, z); 46 } 47 cout << dijkstra() << endl; 48 return 0; 49 }