kuangbin 最短路专题 - POJ - 2387 Til the Cows Come Home （最短路 Dijkstra 算法）

代码注释很详细，典型的Dijkstra问题，注意细节，看注释。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include <map>#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long
//#define int ll
#define INF 0x3f3f3f3f
using namespace std;
int read()
{
    int w = 1, s = 0;char ch = getchar();while (ch < '0' || ch>'9') {
     if (ch == '-') w = -1; ch = getchar(); }while (ch >= '0' && ch <= '9') {
     s = s * 10 + ch - '0';    ch = getchar(); }return s * w;
//最大公约数
}int gcd(int x,int y) {
    if(x<y) swap(x,y);//很多人会遗忘，大数在前小数在后//递归终止条件千万不要漏了，辗转相除法return x % y ? gcd(y, x % y) : y;
}
int lcm(int x,int y)//计算x和y的最小公倍数
{
    return x * y / gcd(x, y);//使用公式
}
//------------------------ 以上是我常用模板与刷题几乎无关 ------------------------//
const int N = 2010;
const int maxn = 100010;
int n, m;
int Map[N][N];// 存储稠密图
bool vis[N];//用于在更新最短距离时 判断当前的点的最短距离是否确定 是否需要更新
int dijksrta(int t) {
    vis[t] = true;for (int i = 1; i <= n; ++i) {
    int minn = maxn;//因为是求最短路，所以用inf来储存int k = 0;//k存储当前访问的点//这里的j代表的是从1号点开始for (int j = 1; j <= n; ++j) {
    if (!vis[j] && Map[t][j] < minn) {
    minn = Map[t][j];k = j;}  }vis[k] = true;//依次更新每个点所到相邻的点路径值for (int j = 1; j <= n; ++j) {
    if (!vis[j] && minn + Map[k][j] < Map[t][j]) {
    Map[t][j] = minn + Map[k][j];}}}return Map[t][1];
}
int main()
{
    m = read();n = read();for(int i = 1; i <= n; ++i) {
    for(int j = 1; j <= n; ++j) {
    Map[i][j] = maxn;}Map[i][i] = 0;}for (int i = 1; i <= m; ++i) {
    int start = read();int end = read();int val = read();如果发生重边的情况则保留最短的一条边if (Map[start][end] > val) {
    Map[start][end] = val;Map[end][start] = val;}}printf("%d\n", dijksrta(n));return 0;
}