HihoCoder 1081dijkstra最短路算法模板

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010 , M = 20010 ;
int n , m , s , t;
int g[N][N] , dist[N];
bool vis[N];
void dijkstra(int s){
memset(dist , 0x3f , sizeof(dist));
memset(vis , 0 , sizeof(vis));
dist[s] = 0;
for(int i = 1 ; i < n ; i++){
int x = 0;
for(int j = 1 ; j <= n ; j ++){
if(!vis[j] && (x == 0 || dist[j] < dist[x])) x = j ;
}
vis[x] = 1;
for(int y = 1 ; y <= n ; y++){
dist[y] = min(dist[y] , dist[x] + g[x][y]);
}
}
}
int main(){
cin >> n >> m >> s >> t;
memset(g , 0x3f , sizeof(g));
for(int i = 1; i <= n ; i++)
g[i][i] = 0;
for(int i = 1; i <=m ; i++){
int x , y , z;
cin >> x >> y >> z;
g[x][y] = min(g[x][y] , z);
g[y][x] = min(g[y][x] , z);
}
dijkstra(s);
cout << dist[t] << endl;
return 0;
}