C++ 解法, 执行用时: 3ms, 内存消耗: 416K, 提交时间: 2021-08-14 17:34:13

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 110;
int g[N][N];
int n,m;
bool st[N];
int dist[N];
int dijkstra()
{
    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[j]<dist[t]))
                t = j;
         st[t]= true;
        for (int j=1;j<=n;j++)
                dist[j] = min(dist[j],dist[t]+g[t][j]);
    }
                return dist[n];
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    memset(g,0x3f,sizeof g);
    while (m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b] = min(g[a][b],c);
        g[b][a] = min(g[b][a],c);
    }
    int t = dijkstra();
    printf ("%d",t);
    return 0;
}

Java(javac 1.8) 解法, 执行用时: 252ms, 内存消耗: 19160K, 提交时间: 2020-04-27 11:20:45

import java.util.Scanner;

public class Main {
	static Scanner cin = new Scanner(System.in);
	static int[][] dis = new int[110][110];
	
	public static void main(String[] args) {
		int n = cin.nextInt(), m = cin.nextInt();
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				if(i == j) dis[i][j] = 0;
				else dis[i][j] = 0x3f3f3f3f;
			}
		}
		while(m-- > 0) {
			int A = cin.nextInt(), B = cin.nextInt(), C = cin.nextInt();
			dis[A][B] = dis[B][A] = Math.min(C, dis[A][B]);
		}
		for(int k = 1; k <= n; k++) {
			for(int i = 1; i <= n; i++) {
				for(int j = 1; j <= n; j++) {
					dis[i][j] = Math.min(dis[i][k] + dis[k][j], dis[i][j]);
				}
			}
		}
		System.out.println(dis[1][n]);
	}
}