글 읽기 - 예외케이스나 틀린부분 찾아주실 수 있을까요...?

catenary 7년 전 0

11952번인데 일단 예시는 다 통과했고 몇가지 추가로 생각해 봐도 다 맞게 나오는데 42%에서 틀렸다고 나오네요 ㅠㅠ

#include <stdio.h>
#include <vector>
#include <queue>
#include <cstdio>
using namespace std;


typedef pair<long long, long long> ii;
vector<ii> a[1000001];
vector<vector<long long > >B;
long long dist[1000001];
int visited[1000001]={0,};
long long INF = 9876543210123;
long long n, m, K, S;
long long p, q;
int u, v;
int start = 1, end;
int zombie[1000001]={0,};
priority_queue<pair< int, int>>pq;
queue<int> qu;
int check[1000001] = { 0, };

long long dijkstra(int start, int end);

int main(void)
{


	for (int i = 0; i<1000001; i++)
		dist[i] = INF;

	scanf("%d %d %d %d", &n, &m, &K, &S);

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

	for (int i = 0; i<K; i++) {
		scanf("%d", &zombie[i]);
		qu.push(zombie[i]);
	}

	B.resize(n + 1);

	for (int i = 0; i<m; i++) {
		scanf("%d %d", &u, &v);
		B[u].push_back(v);
		B[v].push_back(u);
	}
	


	int z;
	for (int i = 0; i < K; i++)
		check[zombie[i]] = 1;

	while (!qu.empty()) {
		int now = qu.front();
		for (z = 0; z<B[now].size(); z++) {
			if (check[B[now][z]] == 0) {
				check[B[now][z]] = check[now] + 1;


				qu.push(B[now][z]);

			}
		}
		qu.pop();
	}


	for (int i = 0; i < K; i++)
		visited[zombie[i]] = 1;

	


	if (check[n] <= S + 1)
		printf("%d\n", dijkstra(1, n) - q);
	else
		printf("%d\n", dijkstra(1, n) - p);

	return 0;
}

long long dijkstra(int start, int end) {

	dist[start] = 0;
	pq.push(ii(0, start));
	while (!pq.empty()) {
		ii t = pq.top();
		pq.pop();
		long long c = t.second;
		if (visited[c] == 1)
			continue;

		visited[c] = 1;
		for (int j = 0; j<(int)B[c].size(); j++) {
			long long n = B[c][j];
			if (check[n] <= S + 1 && visited[n] !=1) {

				if (dist[n] > dist[c] + q)
					dist[n] = dist[c] + q;

				pq.push(ii(-dist[n], n));
			}
			else {
				if (dist[n] > dist[c] + p && visited[n] !=1) {
					dist[n] = dist[c] + p;

				pq.push(ii(-dist[n], n));

			

				}
			}

		}
		
	}

	return dist[end];


}

zlzmsrhak 7년 전 0

최단거리가 4바이트 int 변수의 한계값보다 큰 값이 될 수 있는 것 같습니다.

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

문제

문제

출처

ICPC

예외케이스나 틀린부분 찾아주실 수 있을까요...?

catenary 7년 전 0

zlzmsrhak 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말