글 읽기 - 왜애애애애애 틀린걸까여어어우워워웡

ina97 6년 전 0

도와주세여아으워워어ㅜ어

ㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜ

#include<stdio.h>
#include <queue>
#include <vector>
#include <stdlib.h>

using namespace std;

int n, m, k, s;
int j[100003];
long long dist[100003];
vector < vector < int > > a;
int visit[100003];

int check_zom(int c)
{
	int i;

	for (i = 0; i < k; i++)
	{
		if (j[i] == c) //좀비 점령지이면
			return 1;
	}

	return 0;
}
void ddd(int start, int* safe)
{
	int jj,i;
	priority_queue < pair <long long, int> > pq;

	//행렬 초기화
	for (i = 1; i<=n; i++)
		dist[i] = 987654321987654321;

	dist[start] = 0;
	pq.push(make_pair(0, start));
	safe[start]=0;

	while (!pq.empty())
	{
		int c = pq.top().second;
		pq.pop();

		for (jj = 0; jj< (int)a[c].size(); jj++)
		{
			int tmp = a[c][jj];

			//위험지역 이면 패스
			if (safe[tmp] == 0)
				continue;

			if (dist[tmp] > dist[c] + 1)
			{
				dist[tmp] = dist[c] + 1;
				pq.push(make_pair(-dist[tmp], tmp));
			}
		}
	}

	for (i = 1; i <= n; i++)
	{	
		//이미 위험 지역이었으면 패스
		if (safe[i] == 0)
			continue;

		if (dist[i] <= s)
			safe[i] = 0;

		else
			safe[i] = 1;

	}
}

int main()
{
	int p, q,i;
	int n1, n2;
	int safe[100003];

	scanf("%d %d %d %d", &n, &m, &k, &s);
	a.resize(n + 1);

	scanf("%d %d", &p,&q);

	//좀비 도시 입력
	for (i = 0; i < k; i++)
		scanf("%d", &j[i]);

	//간선 정보 받기
	for (i = 0; i < m; i++)
	{
		scanf("%d %d", &n1, &n2);
		
		a[n1].push_back(n2);
		a[n2].push_back(n1);
	}
	
	//safe 초기화하고 안전도시 확인하기
	for (i = 0; i <= n; i++)
		safe[i] = 1;

	//안전 도시 확인
	for (i = 0; i <k; i++)
		ddd(j[i],safe);

	/*
	for(i=1; i<=n; i++)
		printf("%d = safe %d\n", i, safe[i]);
		*/

	//dist 초기화
	for (i = 0; i <= n; i++)
	{
		visit[i]=0;
		dist[i] = 987654321987654321;
	}

	priority_queue < pair <long long, int> > pq;

	dist[1] = 0;
	visit[1]=1;
	pq.push(make_pair(0, 1));
	
	while(!pq.empty())
	{
		int c; //현재 도시
		
		c = pq.top().second;

		pq.pop();

		for (i = 0; i < (int)a[c].size(); i++)
		{
			int tmp = a[c][i];
			int cost = p;

			if( visit[tmp]==1)
				continue;

			visit[tmp]=1;

			//좀비 점령 도시일 경우 패스
			if (check_zom(tmp) == 1)
				continue;

			//위험도시일 경우
			if (safe[tmp]==0)
				cost = q;

			if (dist[tmp] > dist[c] + cost)
			{
				dist[tmp] = dist[c] + cost;
				pq.push(make_pair(-dist[tmp], tmp));
			}
		}
	}

	if( safe[n]==1)
		printf("%lld\n", dist[n]-p);
	
	else
		printf("%lld\n", dist[n] - q);

	return 0;

}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

왜애애애애애 틀린걸까여어어우워워웡

ina97 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말