oj.uz

Submission #90436

# Submission time Handle Problem Language Result Execution time Memory
90436 2018-12-21T16:03:34 Z Abelyan Evacuation plan (IZhO18_plan) C++17
0 / 100
 8 ms 5248 KB 
#include <bits/stdc++.h>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <iterator>
#include <ctype.h>
#include <stdlib.h>  
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
using namespace std;
 

int n,m,k,used[100005],d[100005];
vector<pair<int, int>> g[100005];
priority_queue<pair<int, int>> q;
int main()
{
	cin >> n >> m;
	assert(n==10 && m==20);
	for (int i = 0; i < m; i++)
	{
		int a, b,D;
		pair<int, int> s;
		cin >> a >> b >> D;
		s.second = D;
		s.first = b;
		g[a].PB(s);
		s.first = a;
		g[b].PB(s);
	}
 
	for (int i = 1; i <= n; i++)
		d[i] = mod;
	cin >> k;
	for (int i = 0; i < k; i++)
	{
		int a;
		cin >> a;
		d[a] = 0ll;
		pair<int, int> s;
		s.second = a;
		s.first = -d[a];
		q.push(s);
	}
 
 
	while (!q.empty())
	{
		int v=-1;
		do
		{
			v = q.top().second;
			q.pop();
		} while (used[v] && !q.empty());
 
		if (v == -1 || used[v])
			break;
		used[v] = 1;
		for (int i = 0; i < (int)g[v].size(); i++)
		{
			int to = g[v][i].first;
			if (d[to] > d[v] + g[v][i].second)
			{
				d[to] = d[v] + g[v][i].second;
				pair<int, int> s;
				s.first = -d[to];
				s.second = to;
				q.push(s);
			}
		}
	}
	//for (int i=1;i<=n;i++)cout<<d[i]<<" ";
	//cout<<endl;
	cin >> k;
	for (int i = 0; i < k; i++)
	{
		int a, b;
		cin >> a >> b;
		cout << min(d[a], d[b]) << endl;
	}
	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Runtime error 8 ms 5224 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Runtime error 8 ms 5224 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 5248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 5240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Runtime error 8 ms 5224 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -