#HASH
Chuyen 1 array sang kieu long long
#define a 96
long long hash(char c[])
{
int i=0;
long long h =0;
while(c[i]!='\0')
{
h=(h<<5)+c[i]-a;
i++;
}
return h;
}
#TRIE
typedef struct TrieNode{
int id;
TrieNode *child[26];
} TrieNode;
TrieNode *createNewNode()
{
TrieNode *p=new TrieNode();
p->id=-1;
for(int i=0;i<26;i++)
{
p->child[i]=NULL;
}
return p;
}
void insert(char c[])
{
TrieNode *p=root;
for(int i=0;c[i];i++)
{
int index =c[i]-'a';
if(p->child[index]==NULL)
{
p->child[index]=createNewNode();
}
p=p->child[index];
}
p->id=index++;
}
void remove(char c[])
{
TrieNode *p=root;
for(int i=0;c[i];i++)
{
int index =c[i]-'a';
if(p->child[index]==NULL)
{
return;
}
p=p->child[index];
}
p->id=-1;
}
bool search(char c[])
{
TrieNode *p=root;
for(int i=0;c[i];i++)
{
if(p>child[index]==NULL)
{
return false;
}
p=p->child[index];
}
return true;
}
#HEAP
int size=0;
int heap[100];
int child, parent;
void push(int value)
{
size++;
heap[size]=value;
child=size;
parent=child/2;
while(parent>=1)
{
if(heap[child]>heap[parent])
{
swap(heap[parent],heap[child]);
child=parent;
parent=child/2;
}
else
{
break;
}
}
}
int pop()
{
int kq=heap[1];
heap[1]=heap[size];
size--;
parent =1;
child=parent*2;
while(child<=size)
{
if(child+1<=size && heap[child+1]>heap[child])
{
child++;
}
if(heap[child]>heap[parent])
{
swap(heap[parent],heap[child]);
parent=child;
child=parent*2;
}
}
return kq;
}
#Hoan vi tap con 12345 54321 42531
int per[N];
int choose[N]=0;
#getPer(0)
void getPer(int i)
{
if(i==N)
{
//show per
return;
}
for(int i1=0;i1<N;i1++)
{
if(!choose[i])
{
per[i]=data[i1];
choose[i]=1;
getPer(i+1);
choose[i]=0;
}
}
}
#tap con
int status[N]=0;
void genSub(int i)
{
if(i==N)
{
//xu ly tap status
return;
}
status[i]=0;
getSub(i+1);
status[i]=1;
genSub(i+1);
}
#BFS
int fron=rear=0;
int Q[N];
void push(int x)
{
Q[front]=x;
front++;
}
int pop()
{
int kq=Q[rear];
rear++;
return kq;
}
bool isEmpty()
{
if(front!=rear) return true;
return false;
}
void bfs()
{
push(x);
visit[x]=1;
while(!isEmpty())
{
int temp=pop();
for(int i=0;i<4;i++)
{
int new_x=temp+d[i];
if(visit[new_x]==0)
{
visit[new_x]=1;
push(new_x);
}
}
}
}
int Matrix[N][N];//xac dinh dinh nao ke voi nhau
int visit[N];
void dfs(int u)
{
visit[u]=1;
for(int i=0;i<N;i++)
{
if(Matrix[u][i]==1 && visit[i]==0)
{
dfs(i);
}
}
}
#Bianry search
typedef struct Node()
{
int key;
Node *left,*right;
} Node;
Node *root=createNewNode(0);
#search
Node *createNewNode(int key)
{
Node *p-new Node();
p->key=key;
p->left=p->right=NULL;
return p;
}
Node *search(Node *root,int value)
{
if(root==NULL || root->key==value)
return root;
if(root->key<value)
return search(root->right,value);
return search(root->left,value);
}
void inorder(*Node root)
{
if(root!=NULL)
{
inorder(root->left);
print(root->index);
inorder(root->right);
}
}
Node *insert(Node *root,int key)
{
if(root==NULL) return insert createNewNode(key);
if(key<root->key)
{
node->left=insert(node->left,key);
}
else if(key>root->key)
{
node->right=insert(node->right,key);
}
return node;
}
Node *delete(Node *root,int key)
{
if(root==NULL) return root;
if(key<root->key)
{
root->left=delete(root->left,key);
}
else if(key>root->key)
{
root->right=delete(root->right,key);
}
//tim thay root va can xoa no
if(root->left==NULL)
{
Node *temp=root->right;
delete root;
return temp;
}
else if(root->right==NULL)
{
Node *temp=root->left;
delete root;
return temp;
}
else//ca 2 node con deu co
{
Node *succseParent=root->right;
Node *succ=root->right;
if(succ->left == NULL)
{
root->key=succ->key;
root->right=succ->right;
delete succ;
return root;
}
else
{
while(succ->left!=NULL)
{
succseParent=succ;
succ=succ->left;
}
//sau khi tim duoc thnag cuoi
root->key=succ->key;
succseParent->left=succ->right;//NULL
delete succ;
return root;
}
}
}
Node *getNodeMin(Node *root)
{
Node *curr=root;
while(curr!=NULL && curr->left !=NULL)
{
curr=curr->left;
}
return curr;
}
int findMinforN(Node* root, int N)
{
// If leaf node reached and is smaller than N
if (root->left == NULL && root->right == NULL
&& root->data < N)
return -1;
// If node's value is greater than N and left value
// is NULL or smaller then return the node value
if ((root->data >= N && root->left == NULL)
|| (root->data >= N && root->left->data < N))
return root->data;
// if node value is smaller than N search in the
// right subtree
if (root->data <= N)
return findMinforN(root->right, N);
// if node value is greater than N search in the
// left subtree
else
return findMinforN(root->left, N);
}
Bạn đã gửi 6 Tháng 12, 2019
// function to find max value less then N
int findMaxforN(Node* root, int N)
{
// Base cases
if (root == NULL)
return -1;
if (root->key == N)
return N;
// If root's value is smaller, try in rght
// subtree
else if (root->key < N) {
int k = findMaxforN(root->right, N);
if (k == -1)
return root->key;
else
return k;
}
// If root's key is greater, return value
// from left subtree.
else if (root->key > N)
return findMaxforN(root->left, N);
}
int N, from, to;
int map[7][7];
int Dijkstra(int from,int to)
{
char visit[MAX];//danh dau
int w[MAX];//luu trong so
//int parent[MAX];//luu thang cha
int XP, min;
//dua ve khoi tao ban dau
for (int i = 1; i < MAX; i++)
{
w[i] = MAX_INT;
visit[i] = 0;
//parent[i] = from;
}
//bat dau tu start
w[from] = 0;//hoac la bang gia tri duoc set
visit[from] = 1;
XP = from;//xp xuat phat
while (XP != to)
{
for (int j = 1; j < MAX; j++)
{
if (map[XP][j] > 0 && w[j] > map[XP][j] + w[XP] && visit[j] == 0)//>0 la co lien ket
{
w[j] = map[XP][j] + w[XP];
//parent[j] = XP;
}
}
//tim gia tri min
min = MAX_INT;
for (int j1 = 1; j1 < MAX; j1++)
{
if (min > w[j1] && visit[j1] == 0)
{
min = w[j1];
XP = j1;
}
}
visit[XP] = 1;
}
//cout << "Duong Di Ngan Nhat La:" << w[to] << endl;
//cout << to << " <- " << parent[to];
//int i = parent[to];
//while (i != from) {
// i = parent[i];
// cout << " <- " << i;
//}
return w[to];
}
int main()
{
freopen("Text.txt", "r", stdin);
cin >> N >> from >> to;
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
cin >> map[i][j];
}
}
int kq= Dijkstra(from,to);
return 0;
}
#HASH chuyen ma hoa cac chuoi String dung trong viec so sanh
long long hash(char c[])
{
long long h=0;
int i=0;
while(c[i])
{
h=(h<<5)+c[i]-96;
i++;
}
return h;
}
#TRIE chuyen dung tuong tu hash de tao ra cac id duy nhat va duyet theo tu dien
typedef struct TrieNode
{
int id;
TrieNode *child[26];
}TrieNode;
int index_trie=0;
TrieNode pull[10000];
TrieNode *createNewNode()
{
TrieNode *p;
if(index_trie<=10000)
{
p=&pull[index_trie];
index_trie++;
}
else
{
p=new TrieNode();
}
p->id=0;
for(int i=0;i<26;i++)
{
p->child[i]=NULL;
}
}
TrieNode *root;
void insert(char c[])
{
TrieNode *p=root;
for(int i=0;c[i];i++)
{
int index=c[i]-'a';
if(p->child[index]==NULL)
{
p->child[index]=createNewNode();
}
p=p->child[index];
}
p->id=index_trie+1;
}
bool remove(char c[])
{
TrieNode *p=root;
for(int i=0;c[i];i++)
{
int index=c[i]-'a';
if(p->index==NULL)
{
return false;
}
p=p->child[index];
}
p->id=1;
}
//HEAP MAXHEAP sap xep theo tto xuong be
int size=0;
int heap[100];
int child,parent;
void push(int value)
{
size++;
heap[size]=value;
child=size;
parent=child/2;
while(parent>=1)
{
if(heap[child]>heap[parent])
{
swap(heap[child],heap[parent]);
child=parent;
parent=child/2;
}
else
{
break;
}
}
}
int pop()
{
int kq=heap[1];
heap[1]=heap[size];
size--;
int child,parent;
parent=1;
child=parent*2;
while(child<=size)
{
if(child+1<=size && heap[child+1]>heap[child])
{
child++;
}
if(heap[child]>heap[parent])
{
swap(heap[child],heap[parent]);
parent=child;
child=parent*2;
}
}
return kq;
}
//BACK TRAC haon vi
int N=10;
int data[N];
int per[N];
int choose[N]={0}
int status[N]={0};
void getPer(int i)
{
if(i==N)
{
showPer();
return;
}
else
{
for(int j=0;j<N;j++)
{
if(!choose[j])
{
choose[j]=1;
per[i]=data[j];
getPer(i+1);
choose[j]=0;
}
}
}
}
void getSub(int i)
{
if(i==N)
{
//show mang status
return;
}
else
{
//voi moi i co 2 trnag thai
status[i]=0;
getSub(i+1);
status[i]=1;
getSub(i+1);
}
}
#BFS
int front=0,rear=0;
int Q[N];
void push(int value)
{
Q[front]=value;
front++;
}
int pop()
{
int temp=Q[rear];
rear++;
return temp;
}
bool isEmpty()
{
if(front!=rear) return true;
return false;
}
void bfs(int value)
{
push(value);
visit[value]=1;
while(!isEmpty())
{
int temp=pop();
for(int i=0;i<4;i++)
{
int new_temp=temp+dx[i];
//xem co dau vao ko
if(visit[new_temp]==0)
{
push(new_temp);
visit[new_temp]=1;
}
}
}
}
//DFS
int MATRIX[N][N]//lien ket giua cac dinh
int visit[N];//danh dau cac dinh da di qua
void dfs(int u)
{
visit[u]=1;
for(int i=0;i<N;i++)
{
if(MATRIX[u][i]==1 && visit[i]==0)
{
dfs(i);
}
}
}
Nhận xét
Đăng nhận xét