POJ 3268 Silver Cow Party

Description

有n个农场（1~N），给出M条单向路描述。每个农场派出一头牛去某个农场（X）参加聚会，聚会结束后要返回，当然它们来回都选择最短路（因为路是单向的，来回可能路径不同），问这n头牛中，来回所走路程最长的那头，它走的总路程是多少?

题目链接 http://poj.org/problem?id=3268

思路

最短路，计算每头牛来回最短路之和，所有和中最大值即为答案

Code

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100005;
const int inf = 0x3f3f3f3f;

int m, n, x;///我程序里的m代表点，n代表边，与题目所述相反

struct edge
{
    int from, to, w, pre;
} a[N];

int head[N], cnt, dis[1005][1005], times[1005], tot, sum;
bool vis[1005];

void init(int start)
{
    for(int i = 0; i <= m; ++i)
        dis[start][i] = inf, times[i] = 0, vis[i] = 0;
    return ;
}

void add(int from, int to, int w)
{
    a[cnt].from = from;
    a[cnt].to = to;
    a[cnt].w = w;
    a[cnt].pre = head[from];
    head[from] = cnt;
    cnt++;
}

bool spfa(int start)///spfa里每个dis第一维下标都是start
{
    deque<int> q;
    dis[start][start] = 0;
    vis[start] = 1;
    q.push_front(start);
    tot = 1;
    sum = 0;
    while(q.size())
    {
        int first = q.front();
        q.pop_front();
        vis[first] = 0;
        tot--;
        sum -= dis[start][first];


        for(int i = head[first]; ~i; i = a[i].pre)
        {
            int t = a[i].to;


            if(dis[start][t] > dis[start][first] + a[i].w)
            {
                dis[start][t] = dis[start][first] + a[i].w;
                if(!vis[t])
                {
                    vis[t] = 1;
                    if(q.empty() || dis[start][t] > dis[start][q.front()] || dis[start][t] * tot >= sum)
                        q.push_back(t);
                    else
                        q.push_front(t);
                    sum += dis[start][t];
                    tot++;
                    if(++times[t] > n)
                        return 0;
                }
            }
        }
    }

    return 1;
}

int main()
{
    while(~scanf("%d%d%d", &m, &n, &x))
    {
        int b, c, d;
        cnt = 0;
        memset(head, -1, sizeof(head));
        for(int i = 0; i < n; ++i)
        {
            scanf("%d%d%d", &b, &c, &d);
            add(b, c, d);
        }

        int ans = 0;
        for(int i = 1; i <= m; ++i)
        {
            init(i);
            if(spfa(i))
            {
                int tem = dis[i][x];
                init(x);
                if(tem != inf && spfa(x))
                {
                    if(dis[x][i] != inf && tem + dis[x][i] > ans)
                        ans = tem + dis[x][i];
                }
            }
        }
        cout << ans << '\n';
    }
    return 0;
}