글 읽기 - 시간초과 문제 무엇이 모르겠습니다ㅠㅠ

thfla0112 4년 전 0

우선 1번 코드(1~77)는 제가 문제를 해결하지 못하여 블로그를 찾아 가져온 코드입니다.
그리고 이것은 채점결과 맞았다고 나왔습니다.

이후 혼자 2번 코드(78~)를 짜보았고 저는 아예 같은 식으로 짯다고 생각했는데 채점결과 계속 시간초과가 계속 나옵니다 ㅠㅠ

제가 어느 부분을 놓치고 있는지 모르겠어서 질문드립니다. ㅠㅠ

///////////1번코드///////////////////


#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int MAX = 20000 + 1;
const int INF = 987654321;

int V, E, K;
vector<pair<int, int>> graph[MAX];

vector<int> dijkstra(int start, int vertex)
{
	vector<int> distance(vertex, INF); 
	distance[start] = 0; 
	priority_queue<pair<int, int>,vector<pair<int, int>>,greater<pair<int, int>>> pq; //Cost, Vertex

	pq.push(make_pair(0, start)); 

	while (!pq.empty())
	{
		int cost = pq.top().first;
		int pre = pq.top().second;
		pq.pop();


		if (distance[pre] < cost)
			continue;

		for (int i = 0; i < graph[pre].size(); i++)
		{
			int curr = graph[pre][i].first;
			int newcost = cost + graph[pre][i].second;

			if (distance[curr] > newcost)
			{
				distance[curr] = newcost;
				pq.push(make_pair(newcost, curr));
			}
		}
	}
	return distance;
}

int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> V >> E >> K;
	V++; //정점번호 1부터 시작



	for (int i = 0; i < E; i++)
	{
		int source, destination, cost;
		cin >> source >> destination >> cost;
		graph[source].push_back(make_pair(destination, cost));
	}

	vector<int> result = dijkstra(K, V);

	for (int i = 1; i < V; i++)
	{
		if (result[i] == INF)
			cout << "INF\n";
		else
			cout << result[i] << "\n";
	}
	return 0;
}

///////////////////2번코드/////////////////
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<vector>
#include<queue>


#define INF 987654321

using namespace std;

int V, E, K;
int W[20001];
vector<vector<pair<int, int>>> Data;


void dijkstra(int S)
{
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Q;
 	W[S] = 0;
	Q.push(make_pair(0, S));
	while (!Q.empty())
	{
		int cost = Q.top().first;
		int nowV = Q.top().second;
		Q.pop();
		if (W[nowV] < cost) continue;
		
		for (int i = 0; i < Data[nowV].size(); i++)
		{
			int curr = Data[nowV][i].second;
			int newcost = Data[nowV][i].first + cost;

			if (W[curr] > newcost)
			{
				W[curr] = newcost;
				Q.push(make_pair(newcost, curr));
			}
		}

	}
}

int main()
{
	int v1, v2, cost;
	scanf("%d %d", &V, &E);
	scanf("%d", &K);
	Data.resize(V + 1);
	for (int i = 1; i <=E; i++)
	{
		scanf("%d %d %d", &v1, &v2, &cost);
		W[i] = INF;
		Data[v1].push_back(make_pair(cost,v2));
	}
	dijkstra(K);

	for (int i = 1; i <= V; i++)
	{
		if (W[i] == INF) printf("INF\n");
		else printf("%d\n", W[i]);
	}
	return 0;
}

3587jjh 4년 전 0

W의 인덱스로 정점 번호를 써야하는데 131째줄에서 인덱스로 간선 번호를 쓰고 있네요

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

문제

문제

출처

ICPC

시간초과 문제 무엇이 모르겠습니다ㅠㅠ

thfla0112 4년 전 0

3587jjh 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말