Submission #90398

#TimeUsernameProblemLanguageResultExecution timeMemory
90398Nodir_BobievEvacuation plan (IZhO18_plan)C++14
23 / 100
752 ms18076 KiB
# include <iostream>
# include <algorithm>
# include <queue>

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

using namespace std;

const long long INF = 1e8 + 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 g[N];
int dist[N];
vector < pair < int, int > > gr[N];

void bfs()
{
	fill(dist, dist + N, INF);
	queue < int > q;
	for (int v = 1; v <= n; v++){
		if(g[v] == 1){
			q.push(v);
			dist[v] = 0;
		}
	}
	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});
	}
	
	cin >> k;
	
	for (int i = 1; i <= k; i++){
		int a; cin >> a;
		g[a] = 1;
	}
	bfs();
	cin >> Q;
	while(Q--){
		int s, t; cin >> s >> t;
		cout << min(dist[s], dist[t]) << endl;
	}
}


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...