Algo2
GRAPH
//// dijackstra
const ll N = 1e5+7;
vector<pair<ll,ll>>g[N];
bool vis[N];
vector<ll>distancee(N,1e18);
ll parent[N];
void djk(ll src) {
set<pair<ll,ll>>sat;
sat.insert({0,src});
distancee[src] = 0;
parent[1] = -1;
while(sat.size()>0)
{
auto pr = *sat.begin();
ll u_wt = pr.ff;
ll u = pr.ss;
sat.erase(sat.begin());
if(vis[u])
{
continue;
}
vis[u] = true;
for(auto &p : g[u])
{
ll v = p.ff;
ll v_wt = p.ss;
if(distancee[u]+v_wt<distancee[v])
{
distancee[v] = distancee[u]+v_wt;
sat.insert({distancee[u]+v_wt,v});
parent[v] = u;
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ll t;
cin >> t;
while(t--)
{
ll n,e,start,endx;
cin >> n >> e >> start >> endx;
while(e--)
{
ll u,v,wt;
cin >> u >> v >> wt;
g[u].pb(make_pair(v,wt));
g[v].pb(make_pair(u,wt));
}
djk(min(start,endx));
if(distancee[max(start,endx)]==1e18)
{
cout << "unreachable" << endl;
}
else
{
cout << distancee[max(start,endx)] << endl;
}
for(ll i=0 ; i<N ; i++)
{
g[i].clear();
vis[i] = false;
parent[i] = 0;
distancee[i] = 1e18;
}
}
}
/////// FLOYAD WARSHAL
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ll n,e,q;
cin >> n >> e >> q;
ll mattrix[n+10][n+10];
for(ll i=1 ; i<=n ; i++)
{
for(ll j=1 ; j<=n ; j++)
{
mattrix[i][j] = 1e18;
if(i==j){ mattrix[i][j] = 0; }
}
}
while(e--)
{
ll u,v,wt;
cin >> u >> v >> wt;
mattrix[u][v] =min(mattrix[u][v],wt);
mattrix[v][u] =min(mattrix[v][u],wt);
}
for(ll k=1 ; k<=n ; k++)
{
for(ll i=1 ; i<=n ; i++)
{
for(ll j=1 ; j<=n ; j++)
{
mattrix[i][j] = min( mattrix[i][j] ,mattrix[i][k]+mattrix[k][j]);
}
}
}
while(q--)
{
ll st,en;
cin >> st >> en;
if(mattrix[st][en]==1e18)
{
cout << -1 << endl;
}
else
{
cout << mattrix[st][en] << endl;
}
}
return 0;
}
///// TOP SORT
const ll N = 110;
vector<ll>g[N];
bool vis[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ll n,e;
cin >> n >> e;
ll indegre[n+10] = {0};
while(e--)
{
ll u,v;
cin >> u >> v;
indegre[v]++;
g[u].pb(v);
}
vector<ll>in_zero;
for(ll i=1 ; i<=n ; i++)
{
if(indegre[i]==0)
{
vis[i] = true;
in_zero.pb(i);
}
}
if(in_zero.size()==0)
{
cout << -1 << endl;
}
else
{
vector<ll>ans;
while(ans.size()<n)
{
ll u = in_zero.back();
ans.pb(u);
in_zero.pop_back();
for(auto &v : g[u])
{
if(!vis[v])
{
indegre[v]--;
if(indegre[v]==0)
{
in_zero.pb(v);
vis[v] = true;
}
}
}
}
for(ll i=0 ; i<ans.size() ; i++)
{
cout << ans[i] << " ";
}
cout << endl;
}
for(ll k=1 ; k<=N ; k++)
{
vis[k] = false;
g[k].clear();
}
return 0;
}
////// MINIMUM KNIGHT MOVES
ll row(string s) {
return (s[0]-'a')+1;
}
ll colum(string s) {
return (s[1]-'1')+1;
}
bool valid(ll x,ll y) {
return (1<=x && x<=8 && 1<=y && y<=8 );
}
const ll N = 10;
ll vis[N][N];
ll Level[N][N];
ll dx[] = {-1,+1,+2,+2,+1,-1,-2,-2};
ll dy[] = {+2,+2,+1,-1,-2,-2,-1,+1};
ll bfs(string start,string endx) {
ll starting_row = row(start);
ll starting_colum = colum(start);
ll end_row = row(endx);
ll end_colum = colum(endx);
queue<pair<ll,ll>>q;
q.push({starting_row,starting_colum});
vis[starting_row][starting_colum] = true;
while(!q.empty())
{
pair<ll,ll>u = q.front();
q.pop();
ll u_x = u.ff;
ll u_y = u.ss;
for(ll i=0 ; i<8; i++)
{
if(valid(u_x+dx[i],u_y+dy[i]) && !vis[u_x+dx[i]][u_y+dy[i]] )
{
q.push({u_x+dx[i],u_y+dy[i]});
vis[u_x+dx[i]][u_y+dy[i]] = true;
Level[u_x+dx[i]][u_y+dy[i]] = Level[u_x][u_y]+1;
}
}
}
return (Level[end_row][end_colum]);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ll t;
cin >> t;
while(t--)
{
string start,endx;
cin >> start >> endx;
cout << bfs(start,endx) << endl;
for(ll i=0 ; i<=N ; i++)
{
for(ll j=0 ; j<=N ; j++)
{
vis[i][j] = false;
Level[i][j] = 0;
}
}
}
}
/// CYCLE DETECTION in directed or undirected graph
bool vis[N];
ll bicolor[N];
ll parent[N];
bool ok = false;
void dfs(ll u) {
vis[u] = true;
for(auto &v : g[u])
{
if(!vis[v])
{
parent[v] = u;
dfs(v);
}
else
{
if(v!=parent[u]) // if the graph is undirected
{
ok = true;
}
if(bicolor[v]==0) // if the graph is directed
{
ok = true;
}
}
}
bicolor[u] = 1;
}
bellman_ford
const ll N = 100;
ll n,e;
vector<pair<ll,ll>>g[N];
vector<ll>distancee(N,1e8);
void bford(ll ux) {
distancee[ux] = 0;
for(ll u=1 ; u<=n ; u++)
{
for(auto &vx : g[u])
{
pair<ll,ll>p = vx;
ll v = p.ff;
ll w = p.ss;
distancee[v] = min(distancee[v],distancee[u]+w);
}
}
}
//0/1 knapsack
#include <bits/stdc++.h>
using namespace std;
int knapSack(int W, int wt[], int val[], int n) {
if (n == 0 || W == 0)
return 0;
if (wt[n - 1] > W)
return knapSack(W, wt, val, n - 1);
else
return max(val[n-1]+knapSack(W-wt[n-1],wt,val,n -1),
knapSack(W, wt, val, n - 1));
}
int main() {
int val[] = { 60, 100, 120 };
int wt[] = { 10, 20, 30 };
int W = 50;
int n = 3;
cout << knapSack(W, wt, val, n);
return 0;
}
Comments
Post a Comment