Topological Sort + Bellman Ford로 O(e) 시간에 풀기

#include <iostream>

#include <fstream>

using namespace std;

int v, e;

struct Link

{

Link(int val, int cost)

{

this->val = val;

this->cost = cost;

next = NULL;

}

int val;

int cost;

Link *next;

};

Link* store = NULL;

Link* graph[500];

int seen[500];

int p[1000];

int d[1000];

void dfs(int i)

{

cout << i << endl;

if(seen[i])

return;

seen[i] = true;

for(Link *temp = graph[i]; temp != NULL; temp = temp->next)

{

dfs(temp->val);

}

if(store == NULL)

{

store = new Link(i, 0);

}

else

{

Link *temp = store;

store = new Link(i, 0);

store->next = temp;

}

}

void topological_sort()

{

for(int i = 1; i <= v; i ++)

dfs(i);

}

void bf(int u, int v, int c)

{

   if (d[v] > d[u] + c)

   { 

  d[v] = d[u] + c;

       p[v] = u; 

   }

}

int main()

{

fstream fin("input.txt");

fin >> v >> e;

for(int i = 0; i < e; i ++)

{

int a, b, c;

fin >> a >> b >> c;

if(graph[a] == NULL)

{

graph[a] = new Link(b, c);

}

else

{

Link *temp = NULL;

for(temp = graph[a]; temp->next != NULL; temp = temp->next);

temp->next = new Link(b, c);

}

}

for(int i = 0; i <= v + 1; i ++) {

d[i] = 987654321;

}

for(int i = 0; i <= e; i ++) {

p[i] = -1;

}

d[0] = 0;

cout << "<--DFS Result-->" << endl;

topological_sort();

cout << "<--Topological Sort Result-->" << endl;

cout << "0" << endl;

for(Link * temp= graph[0]; temp != NULL; temp = temp->next)

{

bf(0, temp->val, temp->cost);

}

for(Link * temp= store; temp != NULL; temp = temp->next)

{

cout << temp->val << endl;

for(Link * head = graph[temp->val]; head != NULL; head = head->next)

{

bf(temp->val, head->val, head->cost);

}

}

cout << "d[i] : " << endl;

for(int i = 0; i <= v + 1; i ++){

cout << d[i] << " ";

}

cout << endl;

}