给一个 n(1≤n≤2500)n(1≤n≤2500) 个点 m(1≤m≤6200)m(1≤m≤6200) 条边的无向图，求 ss 到 tt 的最短路。
Input
第一行四个由空格隔开的整数 nn、mm、ss、tt。
之后的 mm 行，每行三个正整数 sisi、titi、wi(1≤wi≤109)wi(1≤wi≤109)，表示一条从 sisi 到 titi 长度为 wiwi 的边。
Output
一个整数表示从 ss 到 tt 的最短路长度。数据保证至少存在一条道路。
Example
样例输入
7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1
样例输出
7注意：这里采用Dijkstra算法，是为了节约空间，保证程序编译不出错；
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<stack>
#include<cstdio>
using namespace std;
const int MAX=2500+10,inf=0x3f3f3f;
int cost[MAX][MAX];//cost[i][j]表示顶点i到顶点j的权值
int d[MAX];//顶点s出发的最短路径
bool used[MAX];//已经访问过的点
int V;//顶点数
int n,m,s,t;
void Dijkstra(int s){memset(d,inf,sizeof(d));//fill(d,d+V,INF);memset(used,false,sizeof(used));//fill(used,used+V,false);d[s]=0;for(int i=1;i<=V;i++){int mi=inf;for(int i=1;i<=V;i++){if(!used[i]&&d[i]<mi){mi=d[i];s=i;}}used[s]=1;for (int i=1;i<=V;i++){if (cost[s][i]!=inf){d[i]=min(d[i], d[s] + cost[s][i]);}}}
}
void init(){for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)i==j?cost[i][j]=0:cost[i][j]=inf;
}
int main(){scanf("%d%d%d%d",&n,&m,&s,&t);init();V=n;for(int i=0;i<m;i++){int e1,e2,costa;scanf("%d%d%d",&e1,&e2,&costa);cost[e1][e2]=cost[e2][e1]=min(costa,cost[e1][e2]);}Dijkstra(s);printf("%d\n",d[t]);return 0;
}