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;
}

Invitation Cards

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn = 1000005;
int dis[maxn];
int vis[maxn];
int edgehead[maxn];
int a[maxn][3];
struct node{
    int v,w,next;
}edge[maxn];
int start=1;
int k,n,m;
long long sum;
void addedge(int u,int v,int w)
{
    edge[k].v=v;
    edge[k].w=w;
    edge[k].next=edgehead[u];
    edgehead[u]=k++;
}
void init()
{
    memset(dis,inf,sizeof(dis));
    memset(vis,0,sizeof(vis));
    memset(edgehead,0,sizeof(edgehead));
    memset(edge,0,sizeof(edge));
    dis[start]=0;
    k=1;
}
void spfa()
{
    queue<int>q;
    q.push(start);
    vis[start]=1;
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        vis[now]=0;
        for(int i=edgehead[now];i;i=edge[i].next)
        {
            int v=edge[i].v;
            int w=edge[i].w;
            if(dis[v]>dis[now]+w)
            {
                dis[v]=dis[now]+w;
                if(!vis[v])
                {
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        sum+=dis[i];
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=0; i<m; i++)
            scanf("%d%d%d",a[i],a[i]+1,a[i]+2);
        sum=0;
        init();
        for(int i=0; i<m; i++)
            addedge(a[i][0],a[i][1],a[i][2]);
        spfa();
        init();
        for(int i=0; i<m; i++)
            addedge(a[i][1],a[i][0],a[i][2]);
        spfa();
        printf("%lld\n",sum);
    }
    return 0;
}

昂贵的聘礼

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>

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() {
    cin >> m >> n;

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

        int q;
        cin >> g[0][i] >> level[i] >> q;

        while (q -- ) {
            int ver, price;
            cin >> ver >> price;
            g[ver][i] = price;
        }
    }

    int ans = INF;

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

        int 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 min_price = dijkstra();

        if (min_price < ans)
            ans = min_price;
    }

    cout << ans << endl;
    return 0;
}