题目描述
给定一个 nn 个点 mm 条边的有向图，图中可能存在重边和自环，所有边权均为正值。
请你求出 11 号点到 nn 号点的最短距离，如果无法从 11 号点走到 nn 号点，则输出 −1−1。
输入格式
第一行包含整数 nn 和 mm。
接下来 mm 行每行包含三个整数 x,y,zx,y,z，表示存在一条从点 xx 到点 yy 的有向边，边长为 zz。
输出格式
输出一个整数，表示 11 号点到 nn 号点的最短距离。
如果路径不存在，则输出 −1−1。
数据范围
1≤n≤5001≤n≤500,
1≤m≤1051≤m≤105,
图中涉及边长均不超过10000。输入样例：
3 3 1 2 2 2 3 1 1 3 4输出样例：
3
算法求解
分析
模板
注意初始化的时候，初始化为正无穷
循环n-1次，然后每次确定一个点的最短距离
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 510;
int g[N][N]; // 用邻接矩阵存图
int st[N];// st[i] = true 表示i点的最短距离已经确定了
int dist[N]; // 存从1到每个点的最短距离
int n, m;
// 返回从1到n的最短距离
int dijkstra()
{
// 初始化从1到所有点距离为正无穷
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
// 循环n-1次每次取未确定的点里面距离最小的
for(int i = 0; i < n-1; i++)
{
// 从没确定的点里面选一个最小的值 t
int t = -1;
for(int i = 1; i <= n; i++)
if(!st[i] && (t == -1 || dist[i] < dist[t]))
t = i;
// 跟新t指向节点的最短距离
for(int i = 1; i <= n; i++)
// dist[i] = min(dist[i], dist[t] + g[t][i]);
if(!st[i] && dist[i] > dist[t] + g[t][i])
dist[i] = dist[t] + g[t][i];
st[t] = true; //确定了一个点的最短距离
}
if(dist[n] == INF) return -1;
else return dist[n];
}
int main()
{
// 初始化所有点之间边权为无穷大
memset(g, 0x3f, sizeof g);
scanf("%d%d", &n, &m);
while(m--)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a][b] = min(g[a][b], c); // 有重边的话选小的那个
}
int t = dijkstra();
printf("%d\n", t);
return 0;
}