Submission #90402

#TimeUsernameProblemLanguageResultExecution timeMemory
90402Nodir_BobievEvacuation plan (IZhO18_plan)C++14
23 / 100
787 ms18520 KiB
# include <iostream>
# include <algorithm>
# include <queue>

# define ll long long
# define fi first
# define se second

using namespace std;

const long long INF = 2e8 + 10;
const long long MOD = 1e9 + 7;
const long long N = 1e5 + 10;
const long long Z = 5e4 + 10;


int n, m, k, Q;
int dist[N];
vector < pair < int, int > > gr[N];
queue < int > q;

void bfs()
{
	while(!q.empty()){
		int v = q.front();
		q.pop(); 
		for (auto to : gr[v]){
			if(dist[to.fi] > dist[v] + to.se){
				dist[to.fi] = dist[v] + to.se;
				q.push(to.fi);
			}
		}
	}
}

void solve()
{
	cin >> n >> m;
	
	for (int i = 1; i <= m; i++){
		int a, b, w;
		cin >> a >> b >> w;
		gr[a].push_back({b, w});
		gr[b].push_back({a, w});
	}
	fill(dist, dist + N, INF);
	cin >> k;
	
	for (int i = 1; i <= k; i++){
		int a; cin >> a;
		q.push(a);
		dist[a] = 0;
	}
	
	bfs();
	
	cin >> Q;
	while(Q--){
		int s, t; cin >> s >> t;
		cout << min(dist[s], dist[t]) << endl;
	}
	/*
	for (int i = 1; i <= n; i++){
		cout << dist[i] << ' ';
	}*/
}


int main()
{
	int TE = 1;
	ios_base::sync_with_stdio(false);
	//freopen("sort.in", "r", stdin);
	//freopen("sort.out", "w", stdout);
	//cin >> TE;
	while(TE --){
		solve();
	}
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...