http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Index/problemdetail/pid/4049.html
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
int dist[999999],vis[999999]={0};
int tu[2999][2999],n,m;
void dijkstra(int s){
for(int i=1;i<=n;i++){
dist[i] = inf;
vis[i] = 0;
}
dist[s] = 0;
for(int i=1;i<=n;i++){
int ss= -1,mmin=inf;
for(int j=1;j<=n;j++){
if(!vis[j]&&mmin>dist[j]){
mmin = dist[j];
ss = j;
//break;
}
}
if(ss==-1)break;
vis[ss] = 1;
for(int j=1;j<=n;j++){
if(!vis[j]&&dist[ss]+tu[ss][j]<dist[j]){
dist[j] = dist[ss]+tu[ss][j];
}
}
}
}
int main()
{
// int n,m;
cin>>n>>m;
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++){
tu[i][j] = inf;
}
tu[i][i] = 0;
}
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
if(w<tu[u][v]){
tu[u][v] = w;
tu[v][u] = w;
}
}
int s,t;
cin>>s>>t;
dijkstra(s);
// cout<<dijkstra(s,t)<<endl;
if(dist[t]==inf)dist[t] = -1;
cout<<dist[t]<<endl;
// for(int i=1;i<=n;i++){
//
//
// }
return 0;
}
/***************************************************
User name: jk160505徐红博
Result: Accepted
Take time: 148ms
Take Memory: 8084KB
Submit time: 2019-08-28 22:05:36
****************************************************/