[USACO18DEC]Fine Dining

题目描述

漫长的一天结束了，饥困交加的奶牛们准备返回牛棚。

农场由 $a_iai 和 b_ibi，通过需要时间 t_iti。每头奶牛都可以经过一些小路回到牛棚。$

由于饥饿，奶牛们很乐于在他们回家的路上停留一段时间觅食。农场里有 $y_iyi。每头奶牛都想要在她回牛棚的路上在某一个干草捆处停留，但是她这样做仅当经过这个干草捆使她回牛棚的时间增加不超过这个干草捆的美味值。注意一头奶牛仅仅“正式地”在一个干草捆处因进食而停留，即使她的路径上经过其他放有干草捆的牧场；她会简单地无视其他的干草捆。$

输入输出格式

输入格式：

输入的第一行包含三个空格分隔的整数 $a_iai，b_ibi 和 t_iti，表示牧场 a_iai和 b_ibi 之间有一条需要 t_iti 时间通过的小路（a_iai 不等于 b_ibi，t_iti 为不超过 10^4104 的正整数）。$

以下 $10^9109 的正整数）。同一片牧场中可能会有多个干草捆。$

输出格式：

输出包含

输入样例#1：

输出样例#1

1
1
1

题意：

　　中文题意不作解释

分析：

　　首先想到以n为起点跑一遍最短路记为dis1[i]。设f[i]为i点处的干草垛到n点的最短距离，那么就可以枚举每个点经过哪一个干草垛到n点距离最短并记为dis2[i]。比较一下dis1[i]和dis2[i]的大小就可以了。这样做复杂度太高，只是枚举就要O(n*k)了。

　　以n为起点跑一次最短路是一定必需的。对于dis2[i]可以考虑建立第n+1个点，将第n+1个点与所有干草垛建立有向边，并把权值设置为dis1[i]-美味值。以第n+1个点为起点跑一遍最短路，这样可以就保证每个点到达n点的路径一定经过干草垛。

///  author:Kissheart  ///
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<vector>
#include<stdlib.h>
#include<math.h>
#include<queue>
#include<deque>
#include<ctype.h>
#include<map>
#include<set>
#include<stack>
#include<string>
#define INF 0x3f3f3f3f
#define FAST_IO ios::sync_with_stdio(false)
const double PI = acos(-1.0);
const double eps = 1e-6;
const int MAX=1e6+10;
const int mod=1e9+7;
typedef long long ll;
using namespace std;
#define gcd(a,b) __gcd(a,b)
inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
inline ll qpow(ll a,ll b){ll r=1,t=a; while(b){if(b&1)r=(r*t)%mod;b>>=1;t=(t*t)%mod;}return r;}
inline ll inv1(ll b){return qpow(b,mod-2);}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll r=exgcd(b,a%b,y,x);y-=(a/b)*x;return r;}
inline ll read(){ll x=0,f=1;char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) x=x*10+c-'0';return x*f;}
//freopen( "in.txt" , "r" , stdin );
//freopen( "data.txt" , "w" , stdout );
ll head[MAX];
ll dis[MAX],cnt;
ll vis[MAX];
ll n,m,k;
struct node1
{
    ll to,next;
    ll w;
}e[MAX<<1];
void add(ll u,ll v,ll w)
{
    e[cnt]=node1{v,head[u],w};
    head[u]=cnt++;
}
struct node
{
    ll dis;
    ll pos;
    bool operator < (const node &x)const
    {
        return x.dis<dis;
    }
};
priority_queue<node>q;
void dijkstra(ll s)
{
    memset(dis,INF,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[s]=0;
    q.push( (node){0,s} );
    while(!q.empty())
    {
        node tmp=q.top();
        q.pop();
        ll x=tmp.pos,d=tmp.dis;

        if(vis[x]) continue;
        vis[x]=1;
        for(ll i=head[x];~i;i=e[i].next)
        {
            ll y=e[i].to;
            if(dis[y]>dis[x]+e[i].w)
            {
                dis[y]=dis[x]+e[i].w;

                if(!vis[y])
                    q.push( (node){dis[y],y} );
            }
        }
    }
}
ll dis2[MAX];
int main()
{
    memset(head,-1,sizeof(head));


    scanf("%lld%lld%lld",&n,&m,&k);
    for(ll i=1;i<=m;i++)
    {
        ll x,y,z;
        scanf("%lld%lld%lld",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
    dijkstra(n);

    for(ll i=1;i<=n;i++)
        dis2[i]=dis[i];

    for(ll i=1;i<=k;i++)
    {
        ll x,y;
        scanf("%lld%lld",&x,&y);
        add(n+1,x,dis2[x]-y);
    }

    dijkstra(n+1);
    for(ll i=1;i<n;i++)
    {
        if(dis2[i]>=dis[i])
            printf("1
");
        else
            printf("0
");
    }
    return 0;
}

View Code