글 읽기 - 도저히 모르겠어서 질문드립니다 ㅠㅠ

jwg8679 6년 전 0

100퍼센트에서 틀렸습니다가 나오는데 제 코드로는 이게 왜 문제인지 도저히 모르겠습니다

반례를 들어주시면 감사하겠습니다 ㅠㅠ

#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#include <functional>
#include <limits.h>
#include <string>

using namespace std;
int a, b, c, d;
// Dijkstra's Algorithm
struct dijkstra{
	dijkstra(int capacity){
		MAX = capacity;
		parent = new int[MAX];
		weight = new int[MAX];
		for (int i = 0; i < MAX; i++){
			weight[i] = INT_MAX;
		}
		adj = new vector< pair<int, int> >[MAX];
		cost = new vector< pair<int, int> >[MAX];
	}

	~dijkstra(){
		delete[] parent;
		delete[] weight;
	}

	void addedge_directed(int src, int dst, int weight){
		adj[src].push_back(make_pair(weight, dst));
	}

	void addcost(int src, int dst, int n){
		cost[src].push_back(make_pair(dst, n));
	}

	void addedge_undirected(int src, int dst, int weight){
		adj[src].push_back(make_pair(weight, dst));
		adj[dst].push_back(make_pair(weight, src));
	}

	// Initialize parent array
	void init_parent(){
		delete[] parent;
		parent = new int[MAX];
	}

	// Initialize weight array
	void init_weight(){
		for (int i = 0; i < MAX; i++)
			weight[i] = INT_MAX;
	}

	// Initialize all except adj list
	void init_all(){
		delete[] parent;
		parent = new int[MAX];
		for (int i = 0; i < MAX; i++)
			weight[i] = INT_MAX;
		while (!pque.empty())
			pque.pop();
	}

	int calculate_dist(int src, int dst){
		weight[src] = 0;
		int cos = 0;
		pair<int, pair<int, int> > myPair = make_pair(weight[src], make_pair(src, cos));
		pque.push(myPair);
		while (!pque.empty()){
			pair<int, pair<int, int> > myPair2 = pque.top();
			pque.pop();
			int nowCost = myPair2.second.second;
			int now = myPair2.second.first;
			// Reached to the destination
			//cout << now << " " << nowCost << endl;
			if (now == dst){
				//cout << nowCost << endl;
				continue;
			}
            int j = 0;
			vector< pair<int, int> >::iterator i;
			for (i = adj[now].begin(); i != adj[now].end(); i++){
				int alt = weight[now] + i->first;
				int ccost = cost[now][j].second;
				if (weight[i->second] >= alt && nowCost + ccost <= c)
				{
					weight[i->second] = alt;
					pque.push(make_pair(alt, make_pair(i->second, nowCost + ccost)));
				}
                j++;
			}
		}
		if (weight[dst] == INT_MAX)
			return -1;
		else
			return weight[dst];

	}

	// Variable area
	int MAX;
	int *parent;
	int *weight;
	vector< pair<int, int> > *cost;
	priority_queue<pair<int, pair<int, int> >, vector<pair<int, pair<int, int> > >, greater< pair<int, pair<int, int> > > > pque;
	// First is weight, Second is destination
	vector< pair<int, int> > *adj;
};
int main(){
	cin >> a;
	for (int i = 0; i < a; i++){
		cin >> b >> c >> d;
		dijkstra djk(200);
		for (int j = 0; j < d; j++){
			int q, qq, qqq, qqqq;
			cin >> q >> qq >> qqq >> qqqq;
			djk.addedge_directed(q, qq, qqqq);
			djk.addcost(q, qq, qqq);
		}
		int ans = djk.calculate_dist(1, b);
		if (ans == -1)
			cout << "Poor KCM" << endl;
		else cout << ans<<endl;
	}
}

kth004 6년 전 2

1
7 10 7
1 2 1 200
2 4 1 100
4 5 1 300
5 3 1 200
3 6 1 1
6 7 1 1
1 3 9 1

이거 반례인거 같아요.

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

문제

문제

출처

ICPC

도저히 모르겠어서 질문드립니다 ㅠㅠ

jwg8679 6년 전 0

kth004 6년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말