Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <stdio.h>
- #include <limits.h>
- #include <math.h>
- #include <queue>
- #include <string.h>
- using namespace std;
- int n;
- vector<pair<int,int> > *graph;
- unsigned long* costs;
- bool* hasHotel;
- class Node{
- public:
- bool operator> ( const Node & rhs ) const
- { return cost < rhs.cost; }
- bool operator == ( const Node & rhs ) const
- { return cost == rhs.cost; }
- bool operator< ( const Node & rhs ) const
- { return cost > rhs.cost; }
- bool operator <= ( const Node & rhs ) const
- { return cost >= rhs.cost; }
- bool operator >= ( const Node & rhs ) const
- { return cost <= rhs.cost; }
- void set(int c, int i){
- cost = c;
- index = i;
- }
- int getCost(){return cost;}
- int getIndex(){return index;}
- private :
- int cost;
- int index;
- };
- void Dijestra(){
- bool visited [n];
- costs = new unsigned long[n];
- int parent[n];
- bool bits[n];
- bits[0] = false;
- for (int i = 1;i < n;i++){
- costs[i] = ULONG_MAX;
- visited[i] = false;
- parent[i] =0;
- bits[i] = false;
- }
- costs[0] = 0;
- parent[0] = 0;
- priority_queue<Node> pr1;
- Node n1 ;
- n1.set(0, 0);
- pr1.push(n1);
- while (!pr1.empty()){
- Node t = pr1.top();
- int index =t.getIndex();
- int parCost = t.getCost();
- pr1.pop();
- visited[index]= true;
- for (int i = 0;i < graph[index].size(); i++){
- pair<int , int> temp = graph[index].at(i);
- if (!visited[temp.first]){
- if (hasHotel[index] && (temp.second+ costs[index]) > 600){
- if (costs[temp.first] >temp.second){
- costs[temp.first] = temp.second;
- parent[temp.first] = index;
- Node nNode;
- nNode.set(temp.second, temp.first);
- pr1.push(nNode);
- bits[index] = true;
- }
- }
- else {
- if (costs[temp.first] >temp.second+ costs[index]){
- costs[temp.first] = temp.second+ costs[index];
- parent[temp.first] = index;
- Node nNode;
- nNode.set(temp.second+ costs[index], temp.first);
- pr1.push(nNode);
- bits[index] = false;
- }
- }
- }
- }
- }
- vector<int> path;
- for (int i = n-1; i != 0;){
- path.push_back(i+1);
- i = parent[i];
- }
- path.push_back(1);
- int count = 0;
- for (int i = path.size() - 1; i >= 0; i--){
- if (hasHotel[path.at(i) - 1] && bits[index]){
- count++;
- tx = -1*costs[path.at(i) - 1];
- cout << tx<<endl;
- }
- }
- if (costs[n-1] > 600)
- cout << -1<<endl;
- else
- if (array[n-1] < 600)
- cout <<0<<endl;
- else
- cout << count<<endl;
- }
- void get(){
- scanf("%d", &n);
- while (n != 0){
- int k;
- scanf("%d", &k);
- hasHotel =new bool [n];
- for (int i =0;i < n;i++)
- hasHotel[i] = false;
- for (int i = 0; i < k;i++){
- int temp;
- scanf("%d", &temp);
- hasHotel[temp-1] = true;
- }
- int edges;
- scanf("%d", &edges);
- graph = new vector<pair<int,int> >[n];
- int from , to, wigth;
- for (int i = 0;i < edges; i++){
- scanf("%d%d%d", &from , &to, &wigth);
- pair<int, int> p1;
- p1.first =to - 1;
- p1.second = wigth;
- graph[from -1].push_back(p1);
- }
- Dijestra();
- delete []hasHotel;
- delete [] costs;
- delete []graph;
- scanf("%d", &n);
- }
- }
- int main()
- {
- get();
- /*graph = new vector<pair<int,int> >[10];
- vector<pair<int,int> > p1;
- pair<int , int> par;
- par.first = 4;
- par.second = 1;
- p1.push_back(par);
- graph[0] = p1;
- pair<int , int> parc = p1.at(0);
- cout << parc.first<<" "<<parc.second<<endl;
- //t();*/
- return 0;
- }
- /*graph = new vector<pair<int,double> >[10];
- vector<pair<int,double> > p1;
- pair<int , double> par;
- par.first = 4;
- par.second = 1.5;
- p1.push_back(par);
- graph[0] = p1;
- t();*/
Add Comment
Please, Sign In to add comment