Блог пользователя ap_hawkdown

Автор ap_hawkdown, 10 лет назад, По-английски

Simple Dijkstra in C++

Pseudo Code From CLRS:

Dijkstra(G,w,s)

1 -Initialise single source(G,s)

2 -S='\0'

3 -Q=G.V

4 -while Q!='\0'

5 --u=Extract-MIN(Q)

6 --S=S U {u}

7 --for each vertex v belongs to G.Adj[u]

8 ----RELAX(u,v,w)

Function Relax is described in below C++ code

This Blog entry is with reference to problem http://www.spoj.com/problems/EZDIJKST/

/*This is the simplest implemententation of Dijkstra Algorithm in C++. Graph is implemented via STL container list using an adjacency list representation This includes use of STL container Set as a pririty queue thus doing away the need of implementing heaps like in C. */

Code Below:


LL d[1000000];//Distance function list<pair<int,int> > *graph; void dijkstra(int root) { set<pair<int,int> > pq; /* A set helps insertion and extraction operations in logarithmic time. This set maintains (distance,vertex number) pair sorted on basis of distance*/ set<pair<int,int> > ::iterator it; int u,v,wt; list<pair<int,int> > :: iterator i; d[root]=0; pq.insert(pair<int,int>(0,root)); while(pq.size()!=0) { it=pq.begin(); u=it->second; pq.erase(it); for(i=graph[u].begin(); i!=graph[u].end(); i++) { v=i->first; wt=i->second; //Relax u-v edge with weight wt below: if(d[v]>d[u]+wt) { if(d[v]!=1e8) { pq.erase(pq.find(pair<int,int>(d[v],v))); } d[v]=d[u]+wt; pq.insert(pair<int,int>(d[v],v)); } //Relax ends } } } void addedge(int src,int des,int wt) { pair<int,int> x; x.first=des; x.second=wt; graph[src].push_front(x); //here we are consering directed graph so. /* include in case of undirected graph x.first=src; x.second=wt; graph[des].push_front(x); */ //This algorithm works in same way for undirected graph } int main() { int i; int t; cin>>t; while(t--){ int v,e,src,des,wt; cin>>v>>e; //Initialise all d[v] to a large number for(i=0; i<=v; i++) { d[i]=1e8; /*Do not use INF because mathematical operations performed on it will cause overflow in some cases you may need higher values like 1e18 etc. as per constraints */ } graph=new list<pair<int,int> >[v+1]; for(i=0; i<e; i++) { cin>>src>>des>>wt; addedge(src,des,wt); } int x,y; cin>>x>>y; dijkstra(x); if(d[y]!=1e8) cout<<d[y]<<endl; else cout<<"NO"<<endl; } return 0; }

Полный текст и комментарии »

  • Проголосовать: нравится
  • -25
  • Проголосовать: не нравится

Автор ap_hawkdown, 10 лет назад, По-английски

Sieve of Eratosthenes used to determine prime numbers. A bool array in taken and initialized to false
first of all it starts with 2 and updates index of bool array of all multiples of 2 to be true..

like 4,6,8..but not 2 which is kept false. next false number is picked which is 3..and all its multiples are updated true like 6,9,12,15...updated true but 3 is kept false

similarly it is followed..

all numbers in the end which are false are primes.

then next false number is picked

int main() { static bool b[100000];

for(int i=2;i<=30000;i+=1)

{

if(!b[i])

{for(int j=2;j*i<30000;j++)

{

    b[i*j]=true;

}

}

} for(int i=2;i<30000;i++)

{

if(!b[i])

{

printf("%d",i);

}

}

return 0;

}

Полный текст и комментарии »

  • Проголосовать: нравится
  • -11
  • Проголосовать: не нравится