Submission #90384

#	Time	Username	Problem	Language	Result	Execution time	Memory
90384		davitmarg	Evacuation plan (IZhO18_plan)	C++17	0 / 100	4010 ms	15820 KiB

plan

//DavitMarg//
#include <iostream>
#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;

struct street
{
	int to;
	LL d;
};

bool operator<(street a, street b)
{
	return a.d > b.d;
}

int n,m,k,used[100005];
LL d[100005];
vector<street> g[100005];
priority_queue<street> q;
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		d[i] = mod * mod;
	for (int i = 0; i < m; i++)
	{
		int a, b;
		LL D;
		street s;
		cin >> a >> b >> D;
		s.d = D;
		s.to = b;
		g[a].PB(s);
		s.to = a;
		g[b].PB(s);
	}
	cin >> k;
	for (int i = 0; i < k; i++)
	{
		int a;
		cin >> a;
		d[a] = 0;
		street s;
		s.to = a;
		s.d = d[a];
		q.push(s);
	}

	while (!q.empty())
	{
		street v;
		v.d = -1;
		do
		{
			v = q.top();
			q.pop();
		} while (used[v.to]);
		if (v.d == -1)
			break;
		used[v.to] = 1;
		for (int i = 0; i < g[v.to].size(); i++)
		{
			street to = g[v.to][i];
			if (d[to.to] > v.d + to.d)
			{
				d[to.to] = v.d + to.d;
				street s;
				s.d = d[to.to];
				s.to = to.to;
				q.push(s);
			}
		}
	}
	cin >> k;
	for (int i = 0; i < k; i++)
	{
		int a, b;
		cin >> a >> b;
		cout << min(d[a], d[b]) << endl;
	}
	return 0;
}

/*

9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 9
5 9
4 8
7 8
1 2


*/

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:79:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < g[v.to].size(); i++)
                   ~~^~~~~~~~~~~~~~~~

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