//注意陷阱,还有,尽量不要用memset初始化二维数组
#include <iostream> #include <cstring> #include <cstdio> using namespace std; #define INFINITY 100000000 const int maxn = 210; int N,M; int S,T; int G[maxn][maxn]; int Dist[maxn]; bool final[maxn]; void Dijkstra(int v0) { int min; int k; for(int v = 0; v < N; v++) { final[v] = false; Dist[v] = G[v0][v]; } Dist[v0] = 0; final[v0] = true; for(int v = 1; v < N; v++) { min = INFINITY; for(int w = 0; w < N; w++) { if((!final[w]) && Dist[w] < min) { min = Dist[w]; k = w; } } final[k] = 1; for(int w = 0; w < N; w++) { if((!final[w]) && Dist[k] + G[k][w] < Dist[w]) { Dist[w] = Dist[k] + G[k][w]; } } } } int main() { while(cin>>N>>M) { int x,y,d; for(int i = 0; i < N; i++) { G[i][i] = 0; for(int j = 0; j < N ;j ++) { G[i][j] = INFINITY; } } //for(int i = 0; i < N; i++) for(int i = 0; i < M; i++) { cin>>x>>y>>d; if(d < G[x][y]) { G[x][y] = d; G[y][x] = d; } } cin>>S>>T; memset(Dist,INFINITY,sizeof(Dist)); Dijkstra(S); if(final[T]) cout<<Dist[T]<<endl; else cout<<"-1"<<endl; } return 0; }