#include <iostream> #include <cstdio> #include <cstdlib> #define INF 1000000000 #define MX 2005 using namespace std; struct Edge{ int src; int dst; int weight; }; Edge e[MX]; bool bellman(int n,int m,int source) { bool negativecycle =false; int dist[n+5]; dist = 0; for(int i=1;i<n;i++) dist[i]=INF; for(int i=1;i<=n-1;i++) { for(int j=0;j<m;j++) { if(dist[e[j].dst]>dist[e[j].src]+e[j].weight) dist[e[j].dst] = dist[e[j].src]+e[j].weight; } }
Month: February 2015
273
Line Segment Intersection: 1. General Case: a) (p1, q1, p2) and (p1, q1, q2) have different orientations and b) (p2, q2, p1) and (p2, q2, q1) have different orientations 2. Special Case a) (p1, q1, p2), (p1, q1, q2), (p2, q2, p1), and (p2, q2, q1) are all collinear and b) the x-projections of (p1,
924
#include <iostream> #include <string.h> #include <vector> #include <queue> #define ll long long #define INF 10000000 using namespace std; vector<int> vb; vector<int> gr[2501]; int s,n; int daymap[2501]; void bfs(int src) { int day[2501]; bool visit[2501]; for(int i=0;i<2501;i++) { daymap[i]=-1; day[i]=-1; visit[i]=false; } visit[src]=1; day[0]+=1; daymap[src]=0; queue<int> q; q.push(src); int a; while(!q.empty()) { a = q.front(); q.pop();
Miscellaneous
Learning Sites: To learn Click Here Some Problems About Linked List Dynamic Memory Allocation: Code Snippet: int dim; cin>>dim; string **s = new string *[dim]; s[0] = new string[100]; s[1] = new string[100]; s[0][1]="ajksdhjkasdh"; s[1][0]="sswd"; cout<<s[1][0]<<" "<<s[0][1]<<"\n"; BellmanFord Algorithm: Take all the edge in a struct as: Struct Edge{int source,destination,cost}; Relax all the edge for
10044
#include <iostream> #include <string.h> #include <string> #include <vector> #include <cstdio> #include <map> #define ll long long #define MAX_WORD 105 #define INF 100000000 using namespace std; int min_arr[1000001]; map<string,int> nameErdos; int minval(string **vb,int i) { int v = nameErdos[0]]; for(int j=1;vb[i][j]!="END";j++) { v = min(v,nameErdos[j]]); } return v; } int main() { int t,P,N,MN; int kase=1;
10910
Top Down: #include <iostream> #include <cstdio> #include <vector> #include <cstdlib> #define INF 1000 #define ll long long using namespace std; ll res[75][75]; int N,T,P; ll dp(int cnt,int rem) { if(cnt==1 || rem==0) return 1; if(res[cnt][rem]!=-1) return res[cnt][rem]; ll r =0; for(int i=0;i<=rem;i++) { r+= dp(cnt-1,rem-i); } res[cnt][rem]=r; return res[cnt][rem]; } int main() { int t;
10944
#include <iostream> #include <cstdio> #include <vector> #include <cstdlib> #define INF 1000 using namespace std; vector<vector<int> > dp; int dis[25][25]; struct point{ int x; int y; }; point pp[405]; int x,y; int k; string s; bool visit[25]; int location; int MX; /* int trace(int a,int dist) { visit[a]=1; bool f=false; for(int i=1;i<k;i++) { if(!visit[i]) { trace(i,dist+dis[a][i]);