频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
送外卖 拓扑排序+状压DP+最短路
2017-09-11 09:32:14         来源:rgnoH的博客  
收藏   我要投稿

1.注意到K=20,这样的数据范围让人想到状压DP,而且允许进行K次Dijkstra算法。

2.题目中“公司规定了其中某些小区送餐的先后顺序,比如i小区的餐必须在给j小区送餐前送到”释放出明显的拓扑排序信号。

3.设f[i][j]表示在i表示的状态下终点为j时的最小路程和,容易写出状态转移方程:

f[en][j]=min{f[st][k]+dis[k][j]},其中dis[k][j]表示k到j的最短距离,这个可以用最短路算法处理。满足拓扑序列关系时才可以转移

#include
#include
#include
#define ll long long
#define MAXN 20005
#define MAXM 400005
#define Min(x,y) ((x57||s<48))s=getchar();
    if(s=='-')sign=1,s=getchar();
    for(;s>47&&s<58;s=getchar())v=v*10+s-48;
    if(sign)v=-v;
    return v;
}

int en[MAXM],nex[MAXM],las[MAXN],len[MAXM],tot;
void ADD(int x,int y,int z)
{
    en[++tot]=y;
    nex[tot]=las[x];
    las[x]=tot;
    len[tot]=z;
}

int En[MAXM],Nex[MAXM],Las[MAXN],Tot;
void add(int x,int y)
{
    En[++Tot]=y;
    Nex[Tot]=Las[x];
    Las[x]=Tot;
}

ll dis[25][MAXN];
void Dijkstra(int s,int p)
{
    int i,x,y;
    ll z;
    priority_queue >Q;

    for(i=1;i<=N;i++)dis[p][i]=2e9;
    dis[p][s]=0;
    Q.push(make_pair(0,s));
    while(Q.size())
    {
        x=Q.top().second;
        z=Q.top().first;
        Q.pop();
        if(dis[p][x]!=-z)continue;
        for(i=las[x];i;i=nex[i])
        {
            y=en[i];
            if(dis[p][y]>dis[p][x]+len[i])
            {
                dis[p][y]=dis[p][x]+len[i];
                Q.push(make_pair(-dis[p][y],y));
            }
        }
    }
}

int D[400];
stackS;
int main()
{
    int i,j,k,x,y,z,cnt=0,Size;

    N=_R();M=_R();K=_R();
    for(i=1;i<=M;i++)
    {
        x=_R();y=_R();z=_R();
        ADD(x,y,z);
        ADD(y,x,z);
    }
    T=_R();
    for(i=1;i<=T;i++)
    {
        x=_R();y=_R();
        add(x,y);
        D[y]++;
    }

    for(i=1;i<=K+1;i++)Dijkstra(i,i);

    for(i=2;i<=K+1;i++)if(!D[i])S.push(i);
    while(S.size())
    {
        x=S.top();S.pop();
        for(i=Las[x];i;i=Nex[i])
        {
            y=En[i];
            D[y]--;
            ok[y]=ok[y]|ok[x]|(1<
        
   
点击复制链接 与好友分享!回本站首页
上一篇:opencv快速读写大量图片的方法
下一篇:hibernate三种状态
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站