ACM---TTPS/AlmostShortestPath.cpp at master · Andres1433/ACM---TTPS · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include<iostream>
#include<queue>
#include<utility>
#include<vector>
#include<map>

using namespace std;

struct Edge;
struct Vertex{
  int dato;
  vector<Edge> adjacency;
};

struct Edge{
  int weight;
  Vertex * source;
  Vertex * destination;
};

void link(map<int,Vertex> & graph,int v1,int v2,int aWeight){
  Edge anEdge;
  anEdge.weight=aWeight;
  anEdge.source= &(graph[v1]);
  anEdge.destination= &(graph[v2]);
  graph[v1].adjacency.push_back(anEdge);
}

void addVertex(map<int,Vertex> & graph,int num){
  Vertex v;
  v.dato=num;
  graph.insert(make_pair(num,v)); //porque es un map , sino graph.push_back(v)
}

void removeLink(map<int,Vertex> & graph,int v1,int v2){
  for(vector<Edge>::iterator e=graph[v1].adjacency.begin();e!=graph[v1].adjacency.end();++e){
    if((*(*e).destination).dato==v2){
      graph[v1].adjacency.erase(e);
      break;
    }
  }
}

class CompareElements { //Comparador para min-heap
public:
    bool operator()(pair<int,Vertex> & e1, pair<int,Vertex> & e2)
    {
      return (e1.first > e2.first);
    }
};

void dijkstra(map<int,Vertex> & graph,int s,vector<int> & path){
  priority_queue<pair<int,Vertex>,vector< pair<int,Vertex> >,CompareElements> heap; //pair<int,Vertex> puede sustituirse con un typdef pair<int,Vertex> distV
  vector<int> dv(graph.size(),9999); // inicializo vector de distancias
  vector<int> pv(graph.size(),0); // inicializo vector de camino minimo
  vector<bool> known(graph.size(),false); // inicializo vector de conocidos
  dv[graph[s].dato]=0;
  heap.push(make_pair(0,graph[s]));
  while (!heap.empty()){
    pair<int,Vertex> p=heap.top();
    heap.pop();
    Vertex u=p.second;
    known[u.dato]=true;
    for (vector<Edge>::iterator e=u.adjacency.begin();e!=u.adjacency.end();++e){
      if(!(known[(*(*e).destination).dato])){
        if(((*e).weight + p.first) < dv[(*(*e).destination).dato]){ //(*(*e).destination).dato puede cambiar po Vertex dest=(*(*e).destination).dato
	  dv[(*(*e).destination).dato]=(*e).weight + p.first;
	  pv[(*(*e).destination).dato]=u.dato;
	  heap.push(make_pair((*e).weight + p.first,(*(*e).destination)));
	}
      }
    }
  }
  path=dv;
}

int main(){
  int N,M,startingPoint,destinationPoint,U,V,P;
  cin >> N >> M;
  while (N!=0 && M!=0){
    map<int,Vertex> graphS,graphD;
    for(int i=0;i<N;i++){
      addVertex(graphS,i);
      addVertex(graphD,i);
    }
    cin >> startingPoint >> destinationPoint;
    for(;M>0;M--){
      cin >> U >> V >> P;
      link(graphS,U,V,P);
      link(graphD,V,U,P);
    }
    vector<int> distancesFromStart;
    vector<int> distanceFromDestination;
    dijkstra(graphS,startingPoint,distancesFromStart);
    if (distancesFromStart[destinationPoint]!=9999){
      dijkstra(graphD,destinationPoint,distanceFromDestination);
      for (map<int,Vertex>::iterator v=graphS.begin();v!=graphS.end();++v){
        for(vector<Edge>::iterator e=(*v).second.adjacency.begin();e!=(*v).second.adjacency.end();++e){
          if (distancesFromStart[(*(*e).source).dato]+(*e).weight+distanceFromDestination[(*(*e).destination).dato] == distancesFromStart[destinationPoint]){
            removeLink(graphS,(*(*e).source).dato,(*(*e).destination).dato);
            e--;
          }
        }
      }
      dijkstra(graphS,startingPoint,distancesFromStart);
      int dist=(distancesFromStart[destinationPoint]==9999)?-1:distancesFromStart[destinationPoint];
      cout << dist << endl;
    }
    else{
      cout << -1 << endl;
    }
    cin >> N >> M;
  }
  return 0;
}
/*
7 9
0 6
0 1 1
0 2 1
0 3 2
0 4 3
1 5 2
2 6 4
3 6 2
4 6 4
5 6 1
4 6
0 2
0 1 1
1 2 1
1 3 1
3 2 1
2 0 3
3 0 2
6 8
0 1
0 1 1
0 2 2
0 3 3
2 5 3
3 4 2
4 1 1
5 1 1
3 0 1
0 0
*/