Dijkstra

#include<bits/stdc++.h>
using namespace std;

int n, m;
vector<pair<int,int>> adj[1005];
int cost[1005][1005];
int parent[1005], dist[1005];
int st, en;

void dijkstra(){
	for(int i = 1; i<= n; i++){
		dist[i] = 100000000;
		parent[i] = -1;
	}
	dist[st] = 0;
	vector<int> Q;
	vector<int> :: iterator it;
	Q.push_back(st);
	
	while(!Q.empty()){
		int min_dist = 100000000; int pos = -1;
		for(int i = 0; i < Q.size(); i++){
			if(dist[i] < min_dist){
				min_dist = dist[i];
				pos = i;
			}
		}
		int u = Q[pos];
		Q.erase(Q.begin() + pos);
		
		for(int v = 1; v <= n; v++){
			if(cost[u][v] > 0){
				int tmp = dist[u] + cost[u][v];
				if(tmp < dist[v]){
					dist[v] = tmp;
					parent[v] = u;
					Q.push_back(v);
				}
			}
		}
	}
	cout<<dist[en]<<endl;
}
int main(){
	memset(cost, 0, sizeof(cost));
	cin>>n>>m>>st>>en;
	for(int i = 1; i <= m; i++){
		int u,v,c;
		cin>>u>>v>>c;
		cost[u][v] = c;
		cost[v][u] = c;
		adj[u].push_back({v,c});
		adj[v].push_back({u,c});
	}
	dijkstra();
	return 0;
}

/* 
5 6 2 5
2 5 5
2 3 4
3 5 1
4 3 3
1 2 2
1 4 1
*/