#include <iostream>
#include <stdio.h>
using namespace std;

int adjList[1010][1010];
int adjDist[1010][1010];

int main() {
	int T, N;
	scanf("%d%d", &T, &N);
	int adjNum[1010] = {0};
	for(int i = 0; i < T; i++){
		int f, t, d;
		scanf("%d%d%d", &f, &t, &d);
		if(f == t) continue;
		adjList[f][adjNum[f]] = t;
		adjDist[f][adjNum[f]] = d;
		adjNum[f]++;
		adjList[t][adjNum[t]] = f;
		adjDist[t][adjNum[t]] = d;
		adjNum[t]++;
	}
	int dist[1010];
	int Dist[1010];
	bool used[1010] = {0};
	used[1] = 1;
	dist[1] = 0;
	Dist[1] = 0;
	for(int i = 2; i <= N; i++) dist[i] = 2147483647;
	int added = 1;
	while(1){
		for(int i = 0; i < adjNum[added]; i++){
			if(used[adjList[added][i]]) continue;
			if(dist[added] + adjDist[added][i] < dist[adjList[added][i]]){
				dist[adjList[added][i]] = dist[added] + adjDist[added][i];
			}
		}
		int mn = 2147483647;
		int arg = -1;
		for(int i = 2; i <= N; i++){
			if(!used[i] && dist[i] < mn){
				mn = dist[i];
				arg = i;
			}
		}
		used[arg] = 1;
		Dist[arg] = dist[arg];
		added = arg;
		if(arg == N){
			break;
		}
	}
	printf("%d\n", Dist[N]);
	return 0;
}

• Re:裸的迪杰特斯拉 (1268) zuozhen 2020-11-17 16:30:16