4372103_ac_438ms_3280k.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <vector>
#include <algorithm>
#define MAXN 500

using namespace std;

int map[MAXN][MAXN];
int rmap[MAXN][MAXN];
int n, cnt;
bool visited[MAXN];
vector <int> points;
int id[MAXN];
int nmap[MAXN][MAXN];

void dfs_a(int u)
{
    visited[u] = true;
    for (int i = 0; i < n; i++)
    {
        if (!visited[i] && map[u][i] != 0)
        {
            dfs_a(i);
        }
    }
    points.push_back(u);
}

void dfs_b(int u)
{
    id[u] = cnt;
    visited[u] = true;
    for (int i = 0; i < n; i++)
    {
        if (!visited[i] && rmap[u][i] != 0)
        {
            dfs_b(i);
        }
    }
}

void getNewGraph()
{

    memset(nmap, 0, sizeof nmap);

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (id[i] != id[j] && map[i][j] != 0)
            {
                if (nmap[id[i]][id[j]] == 0 || nmap[id[i]][id[j]] > map[i][j])
                {
                    nmap[id[i]][id[j]] = map[i][j];
                }
            }
        }
    }
}

void dijkstra(int st, int ed)
{
    bool *used = new bool[cnt];
    int *dis = new int[cnt];

    for (int i = 0; i < cnt; i++)
	{
		dis[i] = -1;
		used[i] = false;
	}
    dis[st] = 0;

    while (!used[ed])
    {
        int min = 0xffffff;
        int p = -1;
        for (int i = 0; i < cnt; i++)
        {
            if (dis[i] != -1 && dis[i] < min && !used[i])
            {
                min = dis[i];
                p = i;
            }
        }
        if (p == -1)
        {
            break;
        }
        used[p] = true;
        for (int i = 0; i < cnt; i++)
        {
            if (nmap[p][i] != 0 && !used[i])
            {
                int tmp = min + nmap[p][i];
                if (dis[i] == -1 || dis[i] > tmp)
                {
                    dis[i] = tmp;
                }
            }
        }
    }
    if (dis[ed] == -1)
    {
        puts("Nao e possivel entregar a carta");
    }
    else
    {
        printf("%d\n", dis[ed]);
    }
    delete []used;
    delete []dis;
}

int main()
{
    int e, h, k;
    int u, v;

    while (true)
    {
        scanf("%d%d", &n, &e);
        if (n == 0 && e == 0)
        {
            break;
        }
        memset(map, 0, sizeof map);
        memset(rmap, 0, sizeof rmap);
        for (int i = 0; i < e; i++)
        {
            scanf("%d%d%d", &u, &v, &h);
            u--;v--;
            if (map[u][v] == 0 || map[u][v] > h)
            {
                map[u][v] = h;
                rmap[v][u] = h;
            }
        }
        fill_n(visited, n, false);
        points.clear();
        for (int i = 0; i < n; i++)
        {
            if (!visited[i])
            {
                dfs_a(i);
            }
        }
        cnt = 0;
        fill_n(visited, n, false);
        for (vector<int>::reverse_iterator it = points.rbegin(); it != points.rend(); ++it)
        {
            int p = *it;

            if (!visited[p])
            {
                dfs_b(p);
                ++cnt;
            }
        }
        getNewGraph();
        scanf("%d", &k);
        while (k-- != 0)
        {
            scanf("%d%d", &u, &v);
            u--;v--;
            if (id[u] == id[v])
            {
                puts("0");
                continue;
            }
            dijkstra(id[u], id[v]);
        }
        puts("");
    }
    return 0;
}