朴素dijkstra(没使用链式前向星，会卡常）

周星宇

[C++] 纯文本查看 复制代码

#include <bits/stsc++.h>      
using namespace std;
const int N = 510;
const int INF = 0x3f3f3f3f;
int n, m;
// 稠密图，邻接矩阵存图
int g[N][N];
// 表示每个点当前，从1号点走到他自己的最短距离
int dist[N];
// 每个点的最短路是否已经确定
int st[N];
int dijkstra(){
   // 初始化距离
   memset(dist, 0x3f, sizeof dist);
   dist[1] = 0;
   // 有n个点所以要进行n次 迭代
   for (int i = 0; i < n; i++){
    	int t = -1;
    	// 找到一个 距离源点最近的点，且这个点还没有确定最短路径st[j]=fasle 
    	for (int j = 1; j <= n; j++){
        	// 当前这个点还没有确定最短路径
        	// 且
        	// 源点到当前这个点的距离是最短的
        	if (st[j] == false && (t == -1 || dist[t] > dist[j])){
           		 // 找到了这个点j
            	t = j;
        	}
    	}
    	// 把t加到st里面去，标记这个点已经确定最短距离
    	st[t] = true;
    	// 用当前这个点更新其他点的距离
    	for (int j = 1; j <= n; j++){
        	// 1到j这个点的距离，和1到t再从t到j这个点的距离比大小
        	dist[j] = min(dist[j], dist[t] + g[t][j]);
    	}
    }
	// 1和n不联通
   if (dist[n] == INF){
    return -1;
   }else{
    return dist[n];
   }
 
}
int main(){
   cin >> n >> m;
   memset(g, 0x3f, sizeof g);
   for(int i=1;i<=m;i++){
    	int a, b, c;
    	cin >> a >> b >> c;
    	// 处理重边，两条边只保留一条距离最短的边 
    	g[a][b] = min(g[a][b], c);
   }cout<<dijkstra();
   return 0;
}

樊泽宇