Submission #159268

#	Time	Username	Problem	Language	Result	Execution time	Memory
159268		sofhiasouza	Evacuation plan (IZhO18_plan)	C++14	10 / 100	4064 ms	16680 KiB

plan

#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;
typedef pair < int, int > ii;

const int maxn = 1e5+10, maxm = 5e5+10;

int n, m, q, k;

int npp[maxn], vist[maxn];

vector < ii > grafo[maxn];

int bfs(int x)
{
	priority_queue < ii, vector < ii >, greater < ii > > fila;

	fila.push({0, x});

	while(fila.size())
	{
		ii aux = fila.top();
		fila.pop();

		int u = aux.second;
		int val = aux.first;

		vist[u] = 1;

		if(npp[u]) return val;

		for(ii y : grafo[u])
		{
			int v = y.first;
			int cst = y.second;

			if(vist[v]) continue;
			
			fila.push({val+cst, v});
		}
	}
}

int32_t main()
{
	cin >> n >> m;

	for(int i = 1 ; i <= m ; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
	
		grafo[a].pb({b, c});
		grafo[b].pb({a, c});
	}

	cin >> k;

	for(int i = 1 ; i <= k ; i++)
	{
		int a;
		cin >> a;
		npp[a] = 1;
	}

	cin >> q;

	for(int i = 1 ; i <= q ; i++)
	{
		int s, t;
		cin >> s >> t;

		memset(vist, 0, sizeof vist);

		int a = bfs(s);

		memset(vist, 0, sizeof vist);

		int b = bfs(t);

		cout << min(a, b) << "\n";
	}
}

Compilation message (stderr)

plan.cpp: In function 'long long int bfs(long long int)':
plan.cpp:43:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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