HDU6252-Subway Chasing(差分约束)

题目链接:hdu6252-Subway Chasing

题意:A,B两个人从家里出发,B提前 x 分钟出发,然后他们在路程中通话 m 次,每次互相告诉自己当前所在的位置,问能否求出每两个点之间的距离。

题解:

​ 差分约束建图用spfa跑是否存在负环,若不存在则有解,反之无解。

参考代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int T,n,m;
ll x;
int cnt[2009];
ll bm[2009];
bool used[2009];
vector< pair<int,ll> > edge[2009];
const ll inf=0x3f3f3f3f3f3f3f3f;
bool spfa(int st)
{
    for(int i=1;    i<=n;   i++)
        bm[i]=inf;
    memset(used,0,sizeof(used));
    memset(cnt,0,sizeof(cnt));//记录从起点到i点的最短距离包含点的个数
    bm[st]=0;   cnt[st]=1;  used[st]=1;
    queue<int> que;
    que.push(st);
    while(!que.empty())
    {
        int u=que.front();
        used[u]=0;  que.pop();
        for(int i=0;    i<edge[u].size();   i++)
        {
            int v=edge[u][i].first;
            int w=edge[u][i].second;
            if(bm[v]>bm[u]+w)
            {
                bm[v]=bm[u]+w;
                cnt[v]=cnt[u]+1;
                if(cnt[v]>n)    return 0;//存在负环
                if(!used[v])
                {
                    que.push(v);
                    used[v]=1;
                }
            }
        }
    }
    return 1;
}
int main()
{
    scanf("%d",&T);
    int icase=0;
    while(T--)
    {
        scanf("%d%d%lld",&n,&m,&x);
        for(int i=1;    i<=n;   i++)
            edge[i].clear();
        for (int i=2;   i<=n;   i++)
            edge[i].push_back(make_pair(i-1,-1));
        bool flag=0;
        for(int i=1;    i<=m;   i++)
        {
            int a,b,c,d;
            scanf("%d%d%d%d",&a,&b,&c,&d);
            if(a==b&&b==c&&c==d)
            {
                flag=1;
                continue;
            }
            else if(a==b&&c==d)
            {
                edge[a].push_back(make_pair(d,x));
                edge[d].push_back(make_pair(a,-x));
            }
            else if(a==b&&a==c)
            {
                edge[d].push_back(make_pair(a,-x-1));
            }
            else if(a==b&&a!=c)
            {
                edge[d].push_back(make_pair(a,-x-1));
                edge[a].push_back(make_pair(c,x-1));
            }
            else if(c==d&&b==d)
            {
                edge[d].push_back(make_pair(a,-x-1));
            }
            else if(c==d&&b!=d)
            {
                edge[d].push_back(make_pair(a,-x-1));
                edge[b].push_back(make_pair(d,x-1));
            }
            else if(a==c&&b==d)
            {
                edge[d].push_back(make_pair(a,-x-1));
            }
            else
            {
                edge[d].push_back(make_pair(a,-x-1));
                edge[b].push_back(make_pair(c,x-1));
            }
        }
        printf("Case #%d: ",++icase);
        if(flag||!spfa(n))   printf("IMPOSSIBLE\n");
        else
        {
            for(int i=2;    i<=n;   i++)
                printf("%lld ",bm[i]-bm[i-1]);
            printf("\n");
        }
    }
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。