Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <list>
- #define INFINITY 9999999
- #define NIL -1
- using namespace std;
- class Dijkstra;
- class Arc;
- class Vertex;
- class Graph;
- class Arc
- {
- public:
- int src;
- int dst;
- int weight;
- Arc (int _src, int _dst, int _weight)
- {
- src = _src;
- dst = _dst;
- weight = _weight;
- }
- ~Arc ()
- {
- src = 0;
- dst = 0;
- weight = 0;
- }
- };
- class Vertex
- {
- public:
- vector<Arc*> arcs;
- Vertex ()
- {
- arcs = vector<Arc*>();
- }
- ~Vertex ()
- {
- for (int i = 0; i < (int) arcs.size(); i++)
- {
- delete arcs[i];
- }
- }
- };
- class Graph
- {
- public:
- vector<Vertex*> vertices;
- Graph()
- {
- vertices = vector<Vertex*>();
- }
- void addVertex ()
- {
- Vertex* v = new Vertex();
- vertices.push_back(v);
- }
- void addArc(int _src, int _dst, int _weight)
- {
- Arc* a = new Arc(_src,_dst, _weight);
- vertices[_src]->arcs.push_back(a);
- }
- int w(int u, int v)
- {
- for (int i = 0; i < (int) vertices[u]->arcs.size(); i++)
- {
- if (vertices[u]->arcs[i]->dst == v)
- {
- return vertices[u]->arcs[i]->weight;
- }
- }
- return INFINITY;
- }
- void printGraph()
- {
- for (int i = 0; i < (int) vertices.size(); i++)
- {
- for (int j = 0; j < (int) vertices[i]->arcs.size(); j++)
- {
- cout << i+1 << " " << vertices[i]->arcs[j]->dst+1 << " " << vertices[i]->arcs[j]->weight << "\t";
- }
- cout << endl;
- }
- }
- ~Graph ()
- {
- for (int i = 0; i < (int) vertices.size(); i++)
- {
- delete vertices[i];
- }
- }
- };
- class Dijkstra
- {
- public:
- int* d;
- int* pi;
- list<int> Q;
- Dijkstra()
- {
- }
- void shortest_paths(Graph* G, int s)
- {
- initialize(G,s);
- Q = addVertices(G);
- while (Q.size() != 0)
- {
- int u = extractCheapest(Q);
- Q.remove(u);
- if (d[u] == INFINITY)
- {
- break;
- }
- for (int i = 0; i < (int) G->vertices[u]->arcs.size(); i++)
- {
- int v = G->vertices[u]->arcs[i]->dst;
- relax(G,u,v);
- }
- }
- }
- void initialize(Graph* G, int s)
- {
- int size = G->vertices.size();
- d = new int[size];
- pi = new int[size];
- for (int i = 0; i < size; i++)
- {
- d[i] = INFINITY;
- pi[i] = NIL;
- }
- d[s] = 0;
- }
- void relax(Graph* G, int u, int v)
- {
- int w = (d[u] + G->w(u,v));
- if (d[v] > w)
- {
- d[v] = w;
- pi[v] = u;
- }
- }
- list<int> addVertices(Graph* G)
- {
- list<int> q;
- for (int i = 0; i < (int) G->vertices.size(); i++)
- {
- q.push_back(i);
- }
- return q;
- }
- int extractCheapest(list<int> Q)
- {
- int minorDist = INFINITY;
- int minorVertex = NIL;
- list<int>::iterator it;
- for (it = Q.begin(); it != Q.end(); it++)
- {
- int dist = d[(*it)];
- if ( dist <= minorDist )
- {
- minorDist = dist;
- minorVertex = (*it);
- }
- }
- return minorVertex;
- }
- void printOutput (int cnt, int _d)
- {
- cout << "Case " << cnt << ": Path =";
- printRecursive(_d);
- cout << "; ";
- cout << d[_d] <<" second delay" << endl;
- }
- void printRecursive(int _d)
- {
- if(pi[_d] == NIL)
- {
- cout << " " << _d + 1;
- }
- else
- {
- printRecursive(pi[_d]);
- cout << " "<< _d + 1;
- }
- }
- ~Dijkstra()
- {
- delete [] d;
- delete [] pi;
- }
- };
- int main ()
- {
- int NI;
- int NE;
- int weight;
- int v;
- int s;
- int d;
- int cnt = 0;
- while (cin >> NI)
- {
- if (NI != 0)
- {
- cnt++;
- Graph* G = new Graph();
- for (int u = 0; u < NI; u++)
- {
- G->addVertex();
- cin >> NE;
- for (int j = 0; j < NE; j++)
- {
- cin >> v;
- cin >> weight;
- G->addArc(u,v-1,weight);
- }
- }
- cin >> s;
- cin >> d;
- Dijkstra* dijkstra = new Dijkstra();
- dijkstra->shortest_paths(G,s-1);
- dijkstra->printOutput(cnt,d-1);
- delete G;
- delete dijkstra;
- }
- else
- {
- cnt = 0;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement