Currency Exchange

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

const int N = 110;

int n, m, s;
double v;
double dist[N];
bool st[N];

struct node {
    int to; // 我想要兑换的货币类
    double p; // 汇率；
    double q; // 佣金
} ;
vector<node> V[N];

bool spfa() {
    memset(st, false, sizeof st);
    memset(dist, 0, sizeof dist);
    queue<int> q;
    q.push(s);
    st[s] = true;
    dist[s] = v;

    while (q.size()) {
        int t = q.front();
        q.pop();
        st[t] = false;

        for (int i = 0; i < V[t].size(); i ++ ) {

            int To = V[t][i].to;
            double P = V[t][i].p, Q = V[t][i].q;

            if (dist[To] < (dist[t] - Q) * P) {
                dist[To] = (dist[t] - Q) * P;

                if (dist[s] > v)
                    return true;

                if (!st[To]) {
                    q.push(To);
                    st[To] = true;
                }
            }
        }
    }

    return false;
}

int main() {
    while (~scanf("%d%d%d%lf", &n, &m, &s, &v)) {
        for (int i = 1; i <= n; i ++ )

            V[i].clear();

        while (m -- ) {
            int a, b;
            double c, d;
            node ans;
            scanf("%d%d", &a, &b);
            scanf("%lf%lf", &c, &d);
            ans.to = b, ans.p = c, ans.q = d;
            V[a].push_back(ans);
            scanf("%lf%lf", &c, &d);
            ans.to = a, ans.p = c, ans.q = d;
            V[b].push_back(ans);


        }

        if (spfa())
            puts("YES");
        else
            puts("NO");
    }


    return 0;
}

Wormholes

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 5210;

int n, m, q;
int h[N], e[N], ne[N], w[N], idx;
int dist[N], cnt[N];
bool st[N];

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

bool spfa() {
    memset(dist, 0, sizeof dist);
    memset(st, false, sizeof st);
    memset(cnt, 0, sizeof cnt);
    queue<int> q;

    for (int i = 1; i <= n; i ++ ) {

        q.push(i);
        st[i] = true;
    }

    while (q.size()) {
        int t = q.front();
        q.pop();
        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i]) {

            int j = e[i];

            if (dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;

                if (cnt[j] >= n)
                    return true;

                if (!st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return false;
}

int main() {
    int T;
    scanf("%d", &T);

    while (T -- ) {
        memset(h, -1, sizeof h);
        idx = 0;
        scanf("%d%d%d", &n, &m, &q);

        while (m -- ) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            add(a, b, c);
            add(b, a, c);
        }

        while (q -- ) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            add(a, b, -c);
        }

        if (spfa())
            puts("YES");
        else
            puts("NO");
    }

    return 0;
}

昂贵的聘礼

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

#define INF 0x3f3f3f3f

int n, m;
int g[N][N];
int level[N];
bool st[N];
int dist[N];

int dijkstra() {
    memset(dist, 0x3f, sizeof dist);

    for (int i = 1; i <= n; i ++ )

        dist[i] = g[0][i];

    for (int i = 1; i <= n; i ++ ) {

        int t = -1;

        for (int j = 1; j <= n; j ++ )

            if (!st[j] && (t == - 1 || dist[j] < dist[t]))
                t = j;
        st[t] = true;

        for (int j = 1; j <= n; j ++ )

            if (!st[j] && g[t][j])
                dist[j] = min(dist[j], dist[t] + g[t][j]);
    }

    return dist[1];
}

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

    for (int i = 1; i <= n; i ++ ) {

        int q;
        scanf("%d%d%d", &g[0][i], &level[i], &q);

        while (q -- ) {
            int ver, price;
            scanf("%d%d", &ver, &price);
            g[ver][i] = price;
        }
    }

    int MAX; // 酋长的等级不一定是最高的
    int min_price = INF;

    for (int i = 1; i <= n; i ++ ) {

        MAX = level[i];

        for (int j = 1; j <= n; j ++ ) {

            if (level[j] > MAX || MAX - level[j] > m)
                st[j] = true;
            else
                st[j] = false;
        }

        int ans = dijkstra();

        if (min_price > ans)
            min_price = ans;
    }

    printf("%d\n", min_price);
    return 0;
}

Frogger

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 210;

#define INF 0x3f3f3f3f

int n;
double g[N][N];
int casei;
double dist[N];
bool st[N];

struct node {
    double x;
    double y;
} spot[N];

double dijkstra() {
    memset(st, false, sizeof st);

    for (int i = 1; i <= n; i ++ )

        dist[i] = INF;
    dist[1] = 0;

    for (int i = 1; i < n; i ++ ) {

        int t = -1;

        for (int j = 1; j <= n; j ++ )

            if (!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        st[t] = true;

        for (int j = 1; j <= n; j ++ )

            dist[j] = min(dist[j], max(dist[t], g[t][j]));
    }

    return dist[2];
}

int main() {
    while (~scanf("%d", &n)) {
        if (n == 0)
            break;

        for (int i = 1; i <= n; i ++ )

            scanf("%lf%lf", &spot[i].x, &spot[i].y);

        for (int i = 1; i <= n; i ++ )

            for (int j = 1; j <= n; j ++ )

                if (i != j)
                    g[i][j] = sqrt(pow(spot[i].x - spot[j].x, 2) + pow(spot[i].y - spot[j].y, 2));
        double ans = dijkstra();
        printf("Scenario #%d\n", ++ casei);
        printf("Frog Distance = %.3lf\n\n", ans);
    }

    return 0;
}

Stockbroker Grapevine

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 110;

#define INF 0x3f3f3f3f

int n;
int g[N][N];

void floyd() {
    for (int k = 1; k <= n; k ++ )

        for (int i = 1; i <= n; i ++ )

            for (int j = 1; j <= n; j ++ )

                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}

int main() {
    while (~scanf("%d", &n)) {
        if (n == 0)
            break;
        memset(g, 0x3f, sizeof g);

        for (int i = 1; i <= n; i ++ ) {

            int x;
            scanf("%d", &x);

            while (x -- ) {
                int b, c;
                scanf("%d%d", &b, &c);
                g[i][b] = c;
            }
        }

        floyd();
        int MIN = INF;
        int flag;

        for (int i = 1; i <= n; i ++ ) {

            int MAX = 0;

            for (int j = 1; j <= n; j ++ )

                if (i != j && MAX < g[i][j])
                    MAX = g[i][j];

            if (MAX < MIN) {
                MIN = MAX;
                flag = i;
            }
        }

        if (MIN < INF)
            printf("%d %d\n", flag, MIN);
        else
            puts("disjoint");
    }

    return 0;
}