【模板】单源最短路2

import java.util.*;

// Dijstra：这里注意点最大5000 可能大于n, 嫌麻烦直接开5000长度
public class Main {
    private static int INF = Integer.MAX_VALUE;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt();
        List<List<int[]>> g = new ArrayList<>(); // 邻接表
        for (int i = 0; i <= 5000; i++) g.add(new ArrayList<>());
        while (m-- > 0) {
            int u = in.nextInt(), v = in.nextInt(), w = in.nextInt();
            g.get(u).add(new int[] {v, w});
            g.get(v).add(new int[] {u, w});
        }
        
        int[] dis = new int[5001]; // dis[i]为 点1 → 点i 的最短路径长度
        Arrays.fill(dis, INF);
        dis[1] = 0;

        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b)->a[1] - b[1]); // 最小堆
        queue.offer(new int[] {1, dis[1]});

        while (!queue.isEmpty()) {
            int[] a = queue.poll();
            int u = a[0], dis1u = a[1];
            if (dis1u > dis[u]) continue; // 之前已经访问过该点u了

            for (int[] b : g.get(u)) { // 尝试更新与 u 相邻的点
                int v = b[0], w = b[1];
                int newDis = dis[u] + w;
                // System.out.printf("%d %d %d\n", u ,v, newDis);
                if (dis[v] > newDis) {
                    // if (v == n) { // 找到n 直接返回？ 不行,可能两个dis[]相同,都能到n,测试用例1
                    //     System.out.println(newDis);
                    //     return;
                    // }
                    dis[v] = newDis;
                    queue.offer(new int[] {v, newDis});
                }
            }
        }
        System.out.println(dis[n] == INF ? -1 : dis[n]); // 未找到？
    }
}

import heapq
n, m = map(int,input().strip().split())
graph = [[] for _ in range(5001)]
for _ in range(m):
    u,v,w = map(int,input().strip().split())
    graph[u].append((v,w))
    graph[v].append((u,w))
dist = [float('inf')]*(5001)
dist[1] = 0
pq = [(0,1)]  # heap中排序的顺序是基于元组中第一个元素的，所以距离在前
while pq:
    d, u = heapq.heappop(pq)
    for v,w in graph[u]:
        if dist[u]+w < dist[v]:
            dist[v] = dist[u] + w
            heapq.heappush(pq,(dist[v],v))
print(dist[n] if dist[n]!=float('inf') else -1)

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
int findmin(int visit[],int dist[],int n){
    int i=0,min=INT_MAX,index;
    for (i=0; i<n; i++) {
         if(!visit[i]&&dist[i]<min){
            index=i;
            min=dist[i];
        }
    }
    return index;
}
int dijkstra(int** g,int src,int end,int n){
    int i=0,u,k=1,j;
    int dist[n],visit[n],min=INT_MAX,path[n];
    for (i=0; i<n; i++) {
        visit[i]=0,dist[i]=min;
    }
    dist[src]=0;
    for (i=1; i<n; i++) {
        u=findmin(visit,dist, n);
        visit[u]=1,path[k++]=u;
        for (j=1;j<n; j++) {
           if(!visit[j]&&g[u][j]&&(dist[u]+g[u][j]<dist[j])){
                 dist[j]=dist[u]+g[u][j];
           }
        }
    }
    if (dist[end]==min) {
        printf("-1");
    }
    else {
        printf("%d",dist[end]);
    }
    return 0;
}
int main() {
    int n,m,i,j,k,a,b,c;
    scanf("%d%d",&n,&m);
    k=n+1;
    int **g=(int**)malloc(sizeof(int*)*5001);
    for (i=0; i<5001; i++) {
        g[i]=(int *)malloc(sizeof(int)*5001);
    }
    for(i=0;i<5001;i++){
        for (j=0;j<5001;j++) {
            g[i][j]=0;
             
        }
    }
    for (i=0; i<m; i++) {
        scanf("%d%d%d",&a,&b,&c);
        g[a][b]=c;
        g[b][a]=c;
    }
    dijkstra(g, 1, k-1, 5001);
    return 0;
 
}

package main

import (
	"fmt"
	"math"
)

//记录1号点到其他点的距离变化过程
var dj [][]int
//记录结果，
var ans []int
//邻接矩阵记录图的信息
var g [][]int
//当作栈使用，记录最新添加进来的顶点
var visit []int
//记录状态
var staue []bool
//初始化邻接矩阵
func create(n, m int, cost [][]int){
    g = make([][]int, n + 1)
    for i := range g{
        g[i] = make([]int, n + 1)
        for j := range g[i]{
            g[i][j] = math.MaxInt
        }
    }
    for i := 0; i < m; i++{
        g[cost[i][0]][cost[i][1]], g[cost[i][1]][cost[i][0]] = cost[i][2], cost[i][2]
    }
}
func solve(n, m int){
    //初始化dj数组
    dj = make([][]int, n + 1)
    for i := range dj{
        dj[i] = make([]int, n + 1)
    }
    //初始化第一列
    for i := 2; i <= n; i++{
        dj[i][2] = g[1][i]
    }
    //初始化ans数组
    ans = make([]int, n + 1)
    //初始化连接数组
    visit = []int{}
    visit = append(visit, 1)
    //初始化状态数组
    staue = make([]bool, n + 1)
    staue[1] = true
    var min, minR int
    //n个点循环n-1次即可寻找到最短路径
    for i := 2; i <= n; i++{
        //每次初始化最小值为无穷大
        min = math.MaxInt
        minR = 0
        //遍历列寻找最小值
        for j := 2; j <= n; j++{
            if !staue[j] && dj[j][i] < min{
                min = dj[j][i]
                minR = j
            }
        }
        if min != math.MaxInt && i != n{
            ans[minR] = min
            staue[minR] = true
            visit = append(visit, minR)
            //加入新顶点后更新最短路径，即后一列
            for k := 2; k <= n; k++{
                newPath := g[visit[len(visit) - 1]][k]
                if newPath == math.MaxInt{
                    dj[k][i + 1] = dj[k][i]
                } else {
                    if newPath + min < dj[k][i]{
                        dj[k][i + 1] = newPath + min
                    } else {
                        dj[k][i + 1] = dj[k][i]
                    }
                }
            }
        } else if min != math.MaxInt && i == n{
            ans[minR] = min
            staue[minR] = true
            visit = append(visit, minR)
        } else if min == math.MaxInt && i == n{
            ans[minR] = -1
        } else {
            //如果最小值是无穷大且不是最后一列，说明多个点不可达，遍历结果数组将结果为初始值的赋值为-1并退出循环
            for i := 2; i <= n; i++{
                if ans[i] == 0{
                    ans[i] = -1
                }
            }
            break
        }
    }
}
func main() {
    var n, m int
    fmt.Scan(&n, &m)
    //cost数组记录边
    cost := make([][]int, m)
    for i := range cost{
        cost[i] = make([]int, 3)
    }
    for i := 0; i < m; i++{
        fmt.Scan(&cost[i][0], &cost[i][1], &cost[i][2])
    }
    create(5000, m, cost)
    solve(5000, m)
    fmt.Println(ans[n])
}只有最后一组用例不能通过，不知道什么问题，输入5000,20000,预期-1，实际0，找不到还有-1的情况了

#include<iostream>
#include<climits>
#include<vector> // 使用INT_MAX所需要引入的头文件
using namespace std;
int main()
{
    const int N = 5000; // 注意题干，图的点数是固定值5000
    vector<vector<int>> G(N+1,vector<int>(N+1)); // 用于模拟邻接矩阵进行建图
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= N; j++)
        {
            G[i][j] = INT_MAX; // 先将邻接矩阵全部初始化为无穷大
        }
    }
    int n, m;
    cin>>n>>m;
    int u, v, w;
    for(int i = 1; i <= m; i++)
    {
        cin>>u>>v>>w;
        G[u][v] = w;G[v][u] = w; // 注意为无向图，需要关于主对角线对称，因此两边都需要存储
    }
    vector<int> dist(N+1); // 用于存储每个顶点当前与源点的最短距离
    vector<bool> flag( N+ 1); // 用于记录每个顶点是否已经完成与源点最短距离的计算处理
    for(int i = 2; i <= N; i++)
    {
        dist[i] = G[1][i];flag[i] = false;
    }
    dist[1] = 0;flag[1] = true; // 将源点加入已处理集合
    for(int i = 2; i <= N; i++)
    {
        int tmp = INT_MAX, index = 1;
        for(int j = 2; j <= N; j++) // 遍历寻找与源点的最短距离
        {
            if(flag[j] == false && dist[j] < tmp)
            {
                tmp = dist[j];
                index = j;
            }
        }
            flag[index] = true; // 找到后将其加入已处理集
        for(int j = 2; j <= N; j++)
        {
            if(flag[j] == false && G[index][j] != INT_MAX)
            {
                if(G[index][j] + dist[index] < dist[j])
                {
                    dist[j] = G[index][j] + dist[index]; // 新的距离比原距离更短，则进行更新
                }
            }
        }
    }
    if(dist[n] != INT_MAX)
    {
        cout<<dist[n];
    }
    else // 没有从源点到达该顶点的边
    {
        cout<<-1;
    }
    return 0;
}

#include <stdio.h>
#include <string.h>

typedef struct graph {
    int matrix[5000][5000];
} graph;

//-1表示无穷大
void init_graph(graph* g) {
    memset(g->matrix, -1, sizeof(g->matrix));
}

void add_edge(graph* g, int start, int end, int cost) {
    if (g->matrix[start - 1][end - 1] > cost || g->matrix[start - 1][end - 1] == -1) {
        g->matrix[start - 1][end - 1] = cost;
        g->matrix[end - 1][start - 1] = cost;
    }
}

//采用dijkstra算法
int dijkstra(graph* g, int start, int end) {
    if(start == end){
        return 0;
    }
    char final[5000];
    memset(final, 0, sizeof(final));
    int distance[5000];
    memset(distance, -1, sizeof(distance));
    int path[5000];
    memset(path, -1, sizeof(path));

    //初始化距离矩阵
    final[start - 1] = 1;
    for (int i = 0; i < 5000; i++) {
        distance[i] = g->matrix[start - 1][i];
    }
    int visited = 1,temp;
    while (visited != 5000) { //还有节点没有加入
        //选择一个到达start的距离最小的且final[]为0的节点
        int cost = -1,idx = -1;
        for (int i = 0 ; i < 5000; i++) {
            if (final[i] == 0 && distance[i] != -1) {
                if(cost == -1 || distance[i] < cost){ 
                    cost = distance[i];
                    idx = i;
                }
            }
        }
        if (idx != -1){
            //将这个点加入final
            final[idx] = 1;
            //计算其他节点同选择的idx节点的距离
            for (int i = 0 ; i < 5000; i++) {
                if (final[i] == 0) {
                    if(g->matrix[i][idx]  != -1 && distance[idx] != -1){
                        temp = g->matrix[i][idx] + distance[idx];
                        if(distance[i] == -1 || temp < distance[i]){ //目标距离start无穷大
                            distance[i] = temp;
                            path[i] = idx;
                        }
                    }
                    
                }
            }
        } else {
            //不需要找了，找不到,全是无穷大的不可到达的点
            break;
        }
        visited++;
    }
    if (path[end - 1] != -1 ) {
        return distance[end - 1];
    }
    return -1;
}

int main() {
    int n,m,start,end,cost;
    scanf("%d%d",&n,&m);
    graph g;
    init_graph(&g);
    for(int i = 0 ; i < m;i++){
        scanf("%d%d%d",&start,&end,&cost);
        add_edge(&g, start, end,cost);
    }
    int ret = dijkstra(&g, 1, n);
    printf("%d\n",ret);
    return 0;
}

#include <iostream>
#include <vector>
#include <climits>
using namespace std;
#define N 5000

int Dijsktra(int n, vector<vector<int>> Graph)
{
    //要构建三个数组
    //一个记录路径大小 Distance
    //一个记录是否已有最小路径 Flag
    //一个记录该点最小路径的前一个点 Previous
    vector<int> Distance;
    vector<bool> Flag(N, false);
  //  vector<int> Previous(N, 0);

    Distance.emplace_back(0);
    for(int i = 1; i < N; i++)
        Distance.emplace_back(Graph[0][i]);
    Flag[0] = true;

    int current = 0 , min;
    for(int i = 1; i < N; i++)
    {
        //当前Distance最小的一个点，即为0到该点的最短路径
        min = INT_MAX;
        for(int j = 0; j < N; j++)
        {
            if( !Flag[j] && Distance[j] < min)
            {
                current = j;
                min = Distance[j];
            }
        }
        Flag[current] = true;

        //更新Distance
        for(int j = 0; j < N; j++)
        {
            //添加条件 Graph[current][j] != INT_MAX以防止溢出
            if( !Flag[j] && Graph[current][j] != INT_MAX && (Graph[current][j] + min < Distance[j] ) )
            {
                Distance[j] = Graph[current][j]+min;
      //          Previous[j] = current;
            }
        }
    }
    //路径仅作练习
    // for(int i = 1; i < N; i++)
    // {
    //     if(!Flag[i])
    //         cout << "0 -> " << i <<" : 不可到达！"<< endl; 
    //     else
    //     {
    //         int x = i;
    //         cout << "0 -> " << i <<" : "<< Distance[i]<<endl;
    //         cout<<" Path: " << i ;
    //         while(Previous[x] != 0)
    //         {
    //             cout << " <- " <<Previous[x];
    //             x = Previous[x];
    //         }
    //         cout <<" <- " <<0 <<endl;
    //     }
    //     cout<<endl;
    // }

    if(Flag[n-1])
        return Distance[n-1];
    return -1;

}

int main() {
    int n, m;
    cin>>n>>m;
    vector<vector<int>> Graph(N, vector<int>(N, INT_MAX));
    int u, v, w;
    while(m--)
    {
        cin >> u >> v >> w;
        Graph[u-1][v-1] = Graph[v-1][u-1] = w;
    }
    int result;
    result = Dijsktra(n,Graph);
    cout << result <<endl;
}

#include <limits.h>
#include <malloc.h>
#include <stdio.h>

#define MAX 5000

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    //使用二维数组存储边的权值，并且行标表示出发点，列标表示到达点
    int map[MAX+1][MAX+1]={0};
    for (int i = 1; i <= MAX; i++) {
        for (int j = 1; j <= MAX; j++) {
                map[i][j] = INT_MAX;
        }
    }
    int u, v, w;
    for (int i = 0; i < m; i++) { // 注意 while 处理多个 case
        scanf("%d %d %d", &u, &v, &w);
        map[u][v] = w;
        map[v][u] = w;
    }

    //Dijkstra算法
    //初始化
    //S表示集合，为1表示在集合中，为0表示不在集合中
    int dist[MAX+1]={0};
    int S[MAX+1]={0};

    for (int i = 1; i <= MAX; i++) {
        dist[i] = map[1][i];
        S[i]=0;
    }
    S[1] = 1;
    dist[1] = 0;

    for(int i=2;i<=n;i++) {
        int min = INT_MAX, min_p=1;
        //找到最小dist
        for (int j = 1; j <=MAX; j++) {
            if (S[j]==0 && min > dist[j]) {
                min = dist[j];
                min_p = j;
            }
        }

        //将min_p节点纳入S
        if(min_p!=1){
            S[min_p]=1;
        }

        for (int j = 1; j <=MAX; j++) {
            if (S[j] == 0 && map[min_p][j] != INT_MAX) { //未纳入S的点,且i能到达j
                int check = map[min_p][j]+dist[min_p];
                //如果1到j的路径较大，则更新
                if (dist[j] > check) {
                    dist[j] = check;
                }
            }
        }
        
    }

    if(dist[n]!=INT_MAX)
        printf("%d", dist[n]);
    else
        printf("-1");
    return 0;
}

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    let [n,m]=(await readline()).split(" ").map(it=>parseInt(it));
    let INF=+Infinity;
    let mat=new Array(5001).fill(0).map(()=>new Array(5001).fill(INF));
    while(m--){
        let [u,v,w]=(await readline()).split(" ").map(it=>parseInt(it));
        mat[u][v]=w;
        mat[v][u]=w;
    }
    let dist=new Array(5001).fill(INF);
    dist[1]=0;
    let vis=new Array(5001).fill(false);
    for(let i=1;i<=5000;i++){
        let x=-1;
        for(let y=1;y<=5000;y++){
            if(!vis[y]&&(x==-1||dist[y]<dist[x])){
                x=y;
            }
        }
        vis[x]=true;
        for(let y=1;y<=5000;y++){
            if(mat[x][y]==INF) continue;
            if(!vis[y]) dist[y]=Math.min(dist[y],dist[x]+mat[x][y]);
        }
    }
    console.log(dist[n]==INF?-1:dist[n]);
}()