题目描述
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 510;
//dist数组存储最短路径,当前距离
int dist[N];
//500个点1e5的边,用邻接矩阵来存储稠密图
int g[N][N];
//布尔数组表示当前位置最短路径是否已经确定
bool st[N];
int n,m;
int dijkstra()
{
//初始最短路,将起点给定0,其余位置初始为无穷表示无法到达的最短路不存在
memset(dist,0x3f,sizeof dist);
dist[1] = 0;
//外层循环
for(int i = 0;i < n - 1;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]);
}
//
if(dist[n] == 0x3f3f3f3f)return -1;
else return dist[n];
}
int main()
{
scanf("%d%d",&n,&m);
//初始邻接矩阵每两个点的距离为无穷,表示两个点之间没有关联
//memset按字节拷贝3f为16进制表示
memset(g,0x3f,sizeof g);
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
g[a][b] = min(c,g[a][b]);//存在重边,取最短的一条即可
}
cout << dijkstra() << endl;
return 0;
}
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla