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