SDOI2009[Elaxia的路线]

先求出那些在公共最短路上的边，并规定方向，对于边<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);

}