WantAirpod

SOL)

다익스트라 알고리즘 조건

• 모든 간선의 가중치가 양수
• 간선+ 가중치

dist배열 ( - : 2147000000) 무한대

pq

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


/*
6 9
1 2 12
1 3 4
2 1 2
2 3 5
2 5 5 
3 4 5
4 2 2
4 5 5 
6 4 5
*/
using namespace std;
struct Edge {
	int vex;
	int dis;
	Edge(int a, int b)
	{
		vex = a;
		dis = b;
	}
	bool operator<(const Edge &b) const
	{//최소힙 가장 작은 값이 상위에 있게함.
		return dis > b.dis;
	}
};
 

int main()
{ 
	priority_queue<Edge> Q;
	vector<pair<int, int>> graph[30];
	int i, n, m, a, b, c;
	cin >> n >> m;
	vector<int> dist(n + 1, 21470000);

	for (i = 1; i <= m; i++)
	{
		cin >> a >> b >> c;
		graph[a].push_back({ b,c });
	}
	Q.push(Edge(1, 0));
	dist[1] = 0;
	while (!Q.empty())
	{
		int now = Q.top().vex;
		int cost = Q.top().dis;
		Q.pop();
		if (cost > dist[now]) continue;
		for (i = 0; i < graph[now].size(); i++)
		{
			int next = graph[now][i].first;
			int nextdis = cost + graph[now][i].second;
			if (dist[next] > nextdis)
			{
				dist[next] = nextdis;
				Q.push(Edge(next, nextdis));
			}
		}


	}//end while

	for (i = 2; i <= n; i++)
	{
		if (dist[i] < 100000)
			cout << i << " : " << dist[i] << endl;
		else
			cout << i << " : " << "IMPOSSIBLE" << endl;

	}


	return 0;
} 

위상정렬

• 일의 선후관계를 유지하면서 그래프를 짜는 알고리즘
• Degree (진입차수배열)을 만든다. 
  • 진입차수의 배열 값은 선행되는 작업의 갯수 
  • 진입차수배열 값이 0이면 선행되는 작업이 없다는 뜻
• Queue를 만들어서 진입차수가 0인 노드를 넣는다.(선행되는작업이없는노드)

dgree

즉, 일을 순서대로 지키면서 BFS를 돌리는 알고리즘이다.

#include <algorithm>
#include <queue>
#include <functional>
#include <vector>
#include <iostream>
using namespace std;
/*
6 6
1 4
5 4
4 3
2 5
2 3
6 2 
*/

int n, m, a, b, score;
int main()
{
	ios_base::sync_with_stdio(false);
	cin >> n >> m;
	
	
	vector<vector<int>>graph(n + 1, vector<int>(n + 1, 0)); 
	vector<int> degree(n + 1);
	queue<int> q;
	for (int i = 0; i < m; i++)
	{ 
		cin >> a >> b;
		graph[a][b] = 1;
		degree[b]++;
	}
	for (int i = 1; i <= n; i++)
	{
		if (degree[i] == 0)
			q.push(i);
	}
	while (!q.empty())
	{
		int now = q.front();
		q.pop();
		cout << now << " ";
		for (int i = 1; i <= n; i++)
		{
			if (graph[now][i] == 1)
			{
				degree[i]--;
				if (degree[i] == 0)
					q.push(i);
			}

		}
	}
	return 0;
}