posted by pflower 2014. 11. 13. 09:55

#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;

}

'공부 > 알고리즘2' 카테고리의 다른 글

Tournament : Bin Packing Problem  (0) 2014.11.20
HIGHEST TOWER BF + TOPOL + GRAPH  (0) 2014.11.13
RACE bellman Ford  (0) 2014.11.06
maxflow bipar  (0) 2014.11.06
maxflow 탈출문제  (0) 2014.11.06