注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Boleyn Su's Blog

 
 
 
 
 

日志

 
 

SDOI2009[Elaxia的路线]  

2010-07-26 17:47:48|  分类: 信息学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

先求出那些在公共最短路上的边,并规定方向,对于边<u,v>,d(x1,u)<d(x1,v)。

然后这些边就组成了一个有向无环图,现在要求的就是这个图上的最长链。

就用动态规划做。

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-7-26

DESCRIPTION:

山东2009年省选 Elaxia的路线

*/

#include <stdio.h>

#include <string.h>

 

const int MAXN=1500;

const int oo=0x7f7f7f7f;

int N,M;

int x1,y1,x2,y2;

int map[MAXN+2][MAXN+2];

int dx1[MAXN+2];

int dy1[MAXN+2];

int dx2[MAXN+2];

int dy2[MAXN+2];

bool graph[MAXN+2][MAXN+2];

bool on_graph[MAXN+2];

bool calced[MAXN+2];

int f[MAXN+2];

void dijkstra(int s,int d[MAXN+2])

{

     bool visited[MAXN+2];

     memset(visited,0,sizeof(visited));

     memset(d,oo,sizeof(int)*(MAXN+2));

     d[s]=0;

     for (int i=0;i<N;i++)

     {

         int minu,dminu=oo;

         for (int u=1;u<=N;u++)

             if (!visited[u]&&d[u]<dminu)

                dminu=d[minu=u];

         visited[minu]=true;

         for (int u=1;u<=N;u++)

             if (!visited[u]&&d[u]>dminu+map[minu][u])

                d[u]=dminu+map[minu][u];

     }

}

int dp(int u)

{

    if (calced[u]) return f[u];

    else

    {

        calced[u]=true;

        for (int v=1;v<=N;v++)

            if (graph[u][v])

               f[u]>?=map[u][v]+dp(v);

        return f[u];

    }

}

int main()

{

    scanf("%d%d%d%d%d%d",&N,&M,&x1,&y1,&x2,&y2);

    memset(map,oo,sizeof(map));

    for (int i=0,u,v,l;i<M;i++)

        scanf("%d%d%d",&u,&v,&l),

        map[u][v]=map[v][u]=l;

    for (int u=1;u<=N;u++) map[u][u]=0;

    dijkstra(x1,dx1);

    dijkstra(y1,dy1);

    dijkstra(x2,dx2);

    dijkstra(y2,dy2);

    for (int u=1;u<=N;u++)

        for (int v=1;v<=N;v++)

            if (u!=v

                &&dx1[u]+map[u][v]+dy1[v]==dx1[y1]

                &&(dx2[u]+map[u][v]+dy2[v]==dx2[y2]

                   ||dy2[u]+map[u][v]+dx2[v]==dx2[y2]))

               on_graph[u]=on_graph[v]=graph[u][v]=true;

    int answer=0;

    for (int u=1;u<=N;u++)

        if (dp(u)>answer) answer=dp(u);

    printf("%d\n",answer);

}

 

  评论这张
 
阅读(580)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018