Floyd-Warshall.cpp

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int INF = 99*999 + 1;

int main() {
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);

	int n, m;
	scanf(" %d %d", &n, &m);

	vector<vector<int> > d(n, vector<int>(n, INF));
	for (int i = 0; i < n; i++) 
		d[i][i] = 0;

	for (int i = 0; i < m; i++) {
		int u, v, w;
		scanf(" %d %d %d", &u, &v, &w); 
		d[u - 1][v - 1] = w;
	}

	for (int k = 0; k < n; k++)
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				if (d[i][k] < INF && d[k][j] < INF)
					d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (d[i][j] != INF)
				printf("%d ", d[i][j]); 
	return 0;
}

Ford-Bellman.cpp

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int INF = 999*999 + 1;

struct Edge {
	int u, v, w;
};

int main() {
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);

	int n, m, s;
	scanf(" %d %d %d", &n, &m, &s);
	vector<Edge> e(m);
	for (int i = 0; i < m; i++) {
		int u, v, w;
		scanf(" %d %d %d", &e[i].u, &e[i].v, &e[i].w);
	}

	vector<int> d(n + 1, INF);
	d[s] = 0;
	for (int i = 0; i < n - 1; i++)
		for (int j = 0; j < m; j++)
			if (d[e[j].u] < INF)
				d[e[j].v] = min(d[e[j].v], d[e[j].u] + e[j].w);

	for (int i = 1; i <= n; i++)
		if (d[i] != INF)
			printf("%d ", d[i]);
	return 0;
}

Incomplete Solution.cpp

#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;

struct S {
    char op;
    int n;
    bool vis;
    S(): vis(false) {}
    S(bool x): vis(x) {}
    S(char o, int x): op(o), n(x), vis(true) {}
};

template<class T> class IndexTranslator {
    vector<T> v;
    int m;
public:
    IndexTranslator(int x): v(2*x + 1, T()), m(x) {}
    T& operator[](int i) { return v[i < 0 ? m - i : i]; }
};

vector<IndexTranslator<S> > m(1000, IndexTranslator<S>::IndexTranslator(1000));
int f;

void p(int i, int j) {
    if (i > 1)
        p(i - 1, m[i][j].n);
    putchar(m[i][j].op);
}

int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    int r, b;
    vector<int> a;
    scanf(" %d", &f);
    a.push_back(f);
    while ((scanf(" %d", &b)) != EOF) 
        a.push_back(b);
    r = a.back();
    a.pop_back();

    m[0][f] = S(true);
    for (int i = 0; i < a.size() - 1; i++)
        for (int j = -1000; j <= 1000; j++) 
            if (m[i][j].vis) {
                if (labs(j + a[i + 1]) <= 1000) 
                    m[i + 1][j + a[i + 1]] = S('+', j);
                if (labs(j - a[i + 1]) <= 1000) 
                    m[i + 1][j - a[i + 1]] = S('-', j);
                if (labs(j*a[i + 1]) <= 1000)
                    m[i + 1][j*a[i + 1]] = S('*', j);
                if (a[i + 1] && labs(j/a[i + 1]) <= 1000)
                    m[i + 1][j/a[i + 1]] = S('/', j);
            }

    if (m[a.size() - 1][r].vis)
        p(a.size() - 1, r);
    else
        puts("IMPOSSIBLE");
    return 0;
}

Knapsack problem.cpp

#include <stdio.h>

int m[10000001], a[40], ans[40];

void p(int i) {
	if (i == 0) return;
	p(i - a[m[i]]);
	ans[m[i]] = 1;
}

int main() {
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);

	int n, w;
	scanf(" %d %d", &n, &w);
	for (int i = 1; i <= w; i++) m[i] = -1;
	for (int i = 0; i < n; i++) {
		scanf(" %d", a + i);
		for (int j = w; j >= a[i]; j--)
			if (m[j - a[i]] != -1 && m[j] == -1) m[j] = i;
	}

	if (m[w] == -1) puts("-1");
	else {
		p(w); 
		for (int i = 0; i < n; i++) printf("%d ", ans[i]);
	}
	return 0;
}

Multiplication Puzzle.cpp

#include <cstdio>
#include <climits>
#include <algorithm>
using namespace std;

const int INF = INT_MAX;

int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    int n;
    scanf(" %d", &n);
    int a[100];
    for (int i = 0; i < n; i++) 
        scanf("%d", a + i);

    int m[100][100];
    for (int i = 0; i < 100; i++)
        for (int j = 0; j < 100; j++)
            m[i][j] = INF;
    for (int i = 0; i < n - 1; i++)
        m[i][i + 1] = 0;

    for (int i = 2; i < n; i++)
        for (int j = 0; j < n - i; j++)
            for (int k = j + 1; k < j + i; k++)
                m[j][j + i] = min(m[j][j + i], m[j][k] + a[j]*a[k]*a[j + i] + m[k][j + i]);

    printf("%d", m[0][n - 1]);
    return 0;
}

Piggy Bank.cpp

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int INF = 9999*10000 + 1;

struct Coin {
	int c, w;
};

int main() {
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);

	int e, f, n, w;
	scanf(" %d %d %d", &e, &f, &n);
	w = f - e;
	vector<Coin> c(n);
	for (int i = 0; i < n; i++) 
		scanf(" %d %d", &c[i].c, &c[i].w);

	vector<int> m(w + 1, INF);
	m[0] = 0;
	for (int i = 1; i <= w; i++)
		for (int j = 0; j < n; j++)
			if (i >= c[j].w)
				m[i] = min(m[i], m[i - c[j].w] + c[j].c);

	printf("%d", m[w] == INF ? -1 : m[w]);
	return 0;
}

Second Problem For HMM.cpp

#include <stdio.h>

struct S {
    int w;
    double p;
    S(): w(0), p(0.0) {}
    S(int a, double b): w(a), p(b) {}
};

double a[100][100], c[100][100];
S w[100][100];

void p(int i, int j) {
    if (i)
        p(i - 1, w[i][j].w);
    printf("%d ", j + 1);
}

int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    int n, m, k;
    scanf(" %d %d %d", &n, &m, &k);
    for (int i = 0; i < n; i++)
        scanf(" %lf", &w[0][i].p);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            scanf(" %lf", &a[i][j]);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            scanf(" %lf", &c[i][j]);

    int s;
    scanf(" %d", &s);
    for (int i = 0; i < n; i++)
        w[0][i].p *= c[i][s - 1];
    for (int i = 1; i < k; i++) {
        scanf(" %d", &s);    
        for (int j = 0; j < n; j++) {
            double cmax = w[i - 1][0].p*a[0][j];
            int maxn = 0;
            for (int k = 1; k < n; k++) {
                double cp = w[i - 1][k].p*a[k][j];
                if (cp > cmax) {
                    cmax = cp;
                    maxn = k;
                }
            }
            w[i][j] = S(maxn, 10*cmax*c[j][s - 1]);
        }
    }
    
    int maxn = 0;
    for (int i = 1; i < n; i++)
        if (w[k - 1][i].p > w[k - 1][maxn].p)
            maxn = i;
    p(k - 1, maxn);
    return 0;
}