Dijkstra.cpp

const long long INF = 100000000000;
vector<char> used (1000010);
vector< vector <int>> gtemp(1000010);


int main(){
//20C Usual Dijkstra 
	int n,m,a,b,ok=0;
	cin >> n >> m;
	++n;
	vector < vector <pair<int, int>> > g(n);
	for (int i = 0; i < m; i++)
	{
		int a, b, w;
		cin >> a >> b >> w;
        ok = 0;
        if (g[a].size() > 0){
            for (int j = 0; j<g[a].size(); j++)
            if (g[a][j].first == b)
            {
                g[a][j].second = min(g[a][j].second,w);
                ok = 1;
            }
            if (ok == 0)
                g[a].push_back(make_pair(b,w));
        }
        else{
            g[a].push_back(make_pair(b, w));
        }
        ok = 0;
        if (g[b].size() > 0){
            for (int j = 0; j<g[b].size(); j++)
            if (g[b][j].first == a)
            {
                g[b][j].second = min(g[b][j].second, w);
                ok = 1;
            }
            if (ok == 0)
                g[b].push_back(make_pair(a,w));
        }
        else{
            g[b].push_back(make_pair(a, w));
        }
       /* g[a].push_back(make_pair(b, w));
		g[b].push_back(make_pair(a, w));*/
	}
    cin >> a >> b;
	int s = a;//1

	vector<long long> d(n, INF), p(n);
	d[s] = 0;
	vector<char> u(n);
	for (int i = 0; i < n; i++)
	{
		int v = -1;
		for (int j = 0; j < n; ++j)//b
		if (!u[j] && (v == -1 || d[j] < d[v]))
			v = j;
		if (d[v] == INF)
			break;
		u[v] = true;

		for (size_t j = 0; j < g[v].size(); ++j)
		{
			int to = g[v][j].first,
				len = g[v][j].second;
			if (d[v] + len < d[to]){
				d[to] = d[v] + len;
				p[to] = v;
			}
		}
	}
    cout << d[b] << endl;
	return 0;
}