글 읽기 - 시간초과

korhippo 4년 전 0

시간초과 나는데

#include<iostream>
#include<vector>
#include<queue>
#include<functional>
using namespace std;

vector<pair<int,int>> vec[20001];
int V, E;
int start;
int INF = 100000000;
int d[20001];

void dijkstra(int start);

int main()
{
	cin >> V >> E;
	cin >> start;
	for (int i = 1; i <= V; i++)
		d[i] = INF;

	for (int i = 0; i < E; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		vec[u].push_back({v,w});
	}
	 
	
	
	dijkstra(start);
	

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

	return 0;
}



void dijkstra(int start)
{
	d[start] = 0;
	priority_queue<pair<int, int>> pq;
	pq.push({start,0});

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

		if (d[now] < cost) continue;
		for (int i = 0; i < vec[now].size() ; i++)
		{
			int next = vec[now][i].first;
			int nextCost = cost + vec[now][i].second;

			if (nextCost < d[next])
			{
				d[next] = nextCost;
				pq.push({next,-nextCost});
			}
		}
	}
}

djm03178 4년 전 3

그래서요?

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

문제

문제

출처

ICPC

시간초과

korhippo 4년 전 0

djm03178 4년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말