2016CCPC FINAL

Solved 132 / 148 A HDU 5999 The Third Cup is Free ---

34 / 70 B HDU 6000 Wash ！！！

优先队列，先找出每个衣服洗完的最小时间，然后洗完衣服最后的最先烘干，烘干也同样优先队列，优先最小值

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<set>
#include<map>
#include<string>
#include<string.h>
#define maxn 10050005
#define ll long long
#include<vector>
#include<queue>
using namespace std;
struct node
{
    ll x,y;
    friend bool operator <(node a,node b)
    {
        return a.x>b.x;
    }
};
priority_queue<node>q1;
priority_queue<node>q2;
ll c[maxn];
int main()
{
    ll t,cas=0;
    scanf("%lld",&t);
    while(t--)
    {
        ll l,n,m;
        scanf("%lld %lld %lld",&l,&n,&m);
        while(!q1.empty()) q1.pop();
        while(!q2.empty()) q2.pop();
        for(ll i=1;i<=n;i++)
        {
            ll x;
            scanf("%lld",&x);
            q1.push({x,x});
        }
        for(ll i=1;i<=m;i++)
        {
            ll x;
            scanf("%lld",&x);
            q2.push({x,x});
        }
        for(ll i=1;i<=l;i++)
        {
            c[i]=q1.top().x;
            node h=q1.top();
            q1.pop();
            q1.push({h.x+h.y,h.y});
        }
        ll ans=0;
        for(ll i=l;i>=1;i--)
        {
            node h=q2.top();
            q2.pop();
            ans=max(ans,c[i]+h.x);
            q2.push({h.x+h.y,h.y});
        }
        printf("Case #%lld: %lld\n",++cas,ans);
    }
}

1 / 1 C HDU 6001 Mr.Panda and Survey ？？？

5 / 10 D HDU 6002 Game Leader？？？

8 / 18 E HDU 6003 Problem Buyer ???

7 / 14 F HDU 6004 Periodical Cicadas ???

Attempted 21 / 46 G HDU 6005 Pandaland ！！！

枚举边进行n次最短路，剪枝：如果最短路过程已经比当前结果大，直接退出

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<set>
#include<map>
#include<string>
#include<string.h>
#define maxn 5005
#define ll long long
#include<vector>
#include<queue>
using namespace std;
const ll inf=1e18;
struct node
{
    ll to,w;
    friend bool operator <(node a,node b)
    {
        return a.w>b.w;
    }
};
struct E
{
    ll to,next,w;
}e[maxn*100];
ll head[maxn*2],cnt=0;
void add(ll u,ll v,ll w)
{
    e[cnt].to=v;
    e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt++;
}
map<pair<ll,ll>,ll> mp;
struct nd
{
    ll x1,y1,x2,y2,w,cnt;
}a[maxn];
ll ans=1e18,m,id;
priority_queue<node>q;
ll dis[maxn*2],vis[maxn*2];
void dijk(ll st,ll del)
{
    while(!q.empty()) q.pop();
    for(int i=0;i<=id+10;i++) dis[i]=inf,vis[i]=0;
    dis[st]=0;q.push({st,0});
    while(!q.empty())
    {
        ll u=q.top().to;q.pop();
        if(vis[u]==1) continue;
        if(dis[u]>ans) return;
        vis[u]=1;
        for(ll i=head[u];i!=-1;i=e[i].next)
        {
            if(i==del||i==del+1) continue;
            ll v=e[i].to,w=e[i].w;
            if(dis[u]+w<dis[v])
            {
                dis[v]=dis[u]+w;
                q.push({v,dis[v]});
            }
        }
    }
}
int main()
{
    ll t,cas=0;
    scanf("%lld",&t);
    while(t--)
    {
        m,id=0;
        scanf("%lld",&m);mp.clear();
        cnt=0,memset(head,-1,sizeof(head));
        for(int i=1;i<=m;i++)
        {
            scanf("%lld %lld %lld %lld %lld",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2,&a[i].w);
            a[i].cnt=cnt;
            ll x1=a[i].x1,y1=a[i].y1,x2=a[i].x2,y2=a[i].y2,w=a[i].w;
            if(mp[{x1,y1}]==0) mp[{x1,y1}]=++id;
            if(mp[{x2,y2}]==0) mp[{x2,y2}]=++id;
            //if(mp[x1][y1]==0) mp[x1][y1]=++id;
            //if(mp[x2][y2]==0) mp[x2][y2]=++id;
            //add(mp[x1][y1],mp[x2][y2],w);add(mp[x2][y2],mp[x1][y1],w);
            add(mp[{x1,y1}],mp[{x2,y2}],w);add(mp[{x2,y2}],mp[{x1,y1}],w);
        }
        ans=1e18;
        for(int i=1;i<=m;i++)
        {
            ll x1=a[i].x1,y1=a[i].y1,x2=a[i].x2,y2=a[i].y2;
            ll u=mp[{x1,y1}],v=mp[{x2,y2}],w=a[i].w,f=a[i].cnt;
            dijk(u,f);
            if(dis[v]==inf) continue;
            ans=min(ans,dis[v]+w);
        }
        printf("Case #%lld: %lld\n",++cas,ans==inf?0:ans);
    }
}

75 / 134 H HDU 6006 Engineer Assignment！！！

34 / 45 I HDU 6007 Mr. Panda and Crystal！！！

Solved 124 / 252 J HDU 6008 Worried School ---

K HDU 6009 Lazors ???

Solved 131 / 230 L HDU 6010 Daylight Saving Time ---

2016CCPC FINAL

原文：https://www.cnblogs.com/League-of-cryer/p/13934341.html