Решение задачи Пекарня с Codeforces

Без пояснения   Просмотров: 18


Маша хочет открыть свою пекарню и печь пирожки в одном из n городов, пронумерованных от 1 до n. Также существует m двунаправленных дорог, каждая из которых соединяет некоторую пару городов. Чтобы печь пирожки, Маше нужно наладить регулярные поставки муки со склада. Всего существует k складов, расположенных в различных городах с номерами a 1, a 2, ..., a k.

К сожалению, законы страны, в которой живет Маша, не позволяют открывать пекарню в любом из городов, где есть склад. Открыть ее можно только в одном из остальных n - k городах, при этом, само собой, за доставку муки нужно платить — за каждый километр пути от склада до пекарни Маша заплатит 1 рубль.

Формально, Маша заплатит x рублей, если она откроет пекарню в городе b ( a i ≠ b для любого 1 ≤ i ≤ k) и выберет склад в городе s ( s = a j для некоторого 1 ≤ j ≤ k), а между городами b и s существует путь по дорогам суммарной длины x (если путей несколько, Маша вправе выбирать, какой именно путь будет использован).

Маша — крайне бережливый и рациональный человек. Ее интересует тот город, при открытии пекарни в котором (и выборе одного из k складов и пути между городом с пекарней и городом со складом) платить за доставку ей придется меньше всего. Помогите Маше найти сумму, которую она заплатит в этом случае.

Код

#include<bits/stdc++.h>
using namespace std;
int n,m,k,v[200000],u[200000],d[200000],a[200000],mn=2e9;
bool b[200000];
int main()
{
	cin>>n>>m>>k;
	for(int i=0;i<m;i++)
		cin>>v[i]>>u[i]>>d[i];
	for(int i=0;i<k;i++)
	{
		cin>>a[i];
		b[a[i]]=1;
	}
	for(int i=0;i<m;i++)
	{
		if(((b[u[i]]&&!b[v[i]])||(b[v[i]]&&!b[u[i]]))&&d[i]<mn)
			mn=d[i];

	}
	if(mn==2e9)
		cout<<-1;
	else
		cout<<mn;
	return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться