제출 #90398

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
90398		Nodir_Bobiev	Evacuation plan (IZhO18_plan)	C++14	23 / 100	752 ms	18076 KiB

plan

# 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;
}

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 0 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 46