Sadonkorjuu

#include <iostream>
#include <string>
#include <chrono>
#include <thread>
#include <list>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <climits>
using namespace std;
template<typename T>

class Graph {
	map<T, list<pair<T, int>>> l;

public:
	void addEdge(T x, T y, int wt) {
		l[x].push_back({y, wt});
		l[y].push_back({x, wt});
	}
	void djikstraSSSP(T src, vector<int>& scores) {

		map<T, int> dist;

		for (auto p : l) {
			T node = p.first;
			dist[node] = INT_MAX;
		}
		dist[src] = 0;

		set<pair<int, T>> s;
		s.insert({dist[src], src});

		while (!s.empty()) {

			pair<int, T> p = *s.begin();
			s.erase(s.begin());
			T currNode = p.second;
			int currNodeDist = p.first;

			for (auto nbr : l[currNode]) {
				T nbrNode = nbr.first;
				int distInBetween = nbr.second;
				int nbrNodeDist = dist[nbrNode];

				if (currNodeDist + distInBetween < nbrNodeDist) {
					auto pr = s.find({dist[nbrNode], nbrNode});
					if (pr != s.end()) {
						s.erase(pr);
					}
					dist[nbrNode] = currNodeDist + distInBetween;
					s.insert({dist[nbrNode], nbrNode});
				}
			}

		}
        int i = 0;
		for (auto x : dist) {
			if (scores[i] != -1) {
				if (scores[i] > x.second) {
					scores[i] = x.second;
				}
			} else {
				scores[i] = x.second;
			}

		++i;
		}
	}

};

int main() {

	Graph<string> g;

	int V = 0;
	cin >> V;
	int i = 0;
	int paths = V-1;
	string roles;
	std::getline(cin >> std::ws, roles);
	vector<int> scores(V, -1);
	while (i < paths) {
		string a,b;
		int c;
		cin >> a >> b >> c;
		g.addEdge(a,b,c);
		++i;
	}
	int j = 1;
	for (char& c : roles) {
		if (string(1,c) == "0") {
			g.djikstraSSSP(std::to_string(j), scores);
			++j;
		} else if (string(1,c) == "1") {
            ++j;
        }

	}
    int totalLength = 0;
	for (int num : scores) {
        totalLength += num;
	}
	cout << totalLength;
}

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 1, 2

Verdict: ACCEPTED

Test 3

Group: 1, 2

Verdict: ACCEPTED

Test 4

Group: 1, 2

Verdict: ACCEPTED

Test 5

Group: 1, 2

Verdict: ACCEPTED

Test 6

Group: 1, 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 1, 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 1, 2

Verdict: TIME LIMIT EXCEEDED

Test 11

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 2

Verdict: WRONG ANSWER

Test 13

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 1, 2

Verdict: ACCEPTED

Test 16

Group: 1, 2

Verdict: ACCEPTED

Test 17

Group: 1, 2

Verdict: TIME LIMIT EXCEEDED

Test 18

Group: 1, 2

Verdict: ACCEPTED

Test 19

Group: 1, 2

Verdict: TIME LIMIT EXCEEDED

Test 20

Group: 1, 2

Verdict: ACCEPTED

Test 21

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 22

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 23

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 24

Group: 1, 2

Verdict: ACCEPTED

Test 25

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 26

Group: 1, 2

Verdict: ACCEPTED

Test 27

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 28

Group: 1, 2

Verdict: ACCEPTED

Test 29

Group: 2

Verdict: ACCEPTED

Test 30

Group: 1, 2

Verdict: ACCEPTED

Test 31

Group: 2

Verdict: TIME LIMIT EXCEEDED