poj3463 最短路和比最短路长1的路径数

这题需要很好的理解Dij。

在Dij的基础上，每个点多一个次短路的长度和数量进行控制。

那么在队列中，最短路控制时出现n次，次短路控制出现n次。注意松弛条件中val值和最短路、次短路的关系。

这题需要了解的是，对vis[i][0]控制确定每个点的最短路长度，对vis[i][1]控制确定每个点的次短路长度。

代码：

#include<iostream>

#include<cstring>

#include<cstdio>

#include<queue>

using namespace std;

#define MAXN 10010

#define inf 100000000

int T,n,m,s,t,temp;

int head[MAXN],dis[MAXN][2],vis[MAXN][2],num[MAXN][2];

struct Node{

    int a;

    int kind;

    int len;

    friend bool operator <(Node a,Node b)

    {

        return a.len>b.len;

    }

}start,v,tem;

struct Edge{

    int u,len,next;

}edge[2*MAXN];

int Dijstra(int s,int t)

{

    priority_queue<Node> que;

    memset(vis,0,sizeof(vis));

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

    {

        dis[i][0]=inf;

        dis[i][1]=inf;

        num[i][0]=0;

        num[i][1]=0;

    }

    while(!que.empty())que.pop();

    start.a=s;

    start.kind=0;

    start.len=0;

    que.push(start);

    dis[s][0]=0;

    num[s][0]=1;

    while(!que.empty())

    {

        v=que.top();

        que.pop();

        if(vis[v.a][v.kind])continue;

        vis[v.a][v.kind]=1;

        for(int i=head[v.a];i!=-1;i=edge[i].next)

        {

            int u=edge[i].u;

            int len=edge[i].len;

            int val=v.len+len;

            if(val<dis[u][0])

            {

                if(dis[u][0]<dis[u][1])

                {

                    dis[u][1]=dis[u][0];

                    num[u][1]=num[u][0];

                    tem.a=u;

                    tem.len=dis[u][1];

                    tem.kind=1;

                    que.push(tem);

                }

                dis[u][0]=val;

                num[u][0]=num[v.a][0];

                tem.a=u;

                tem.len=val;

                tem.kind=0;

                que.push(tem);

            }

            else if(val==dis[u][0])

            {

                num[u][0]+=num[v.a][0];

            }

            else if(val<dis[u][1])

            {

                dis[u][1]=val;

                num[u][1]=num[v.a][v.kind];

                tem.a=u;

                tem.kind=1;

                tem.len=val;

                que.push(tem);

            }

            else if(val==dis[u][1])

            {

                num[u][1]+=num[v.a][v.kind];

            }

        }

    }

    if(dis[t][0]+1==dis[t][1])

        return num[t][0]+num[t][1];

    else return num[t][0];

}

void addEdge(int v,int w,int c)

{

    edge[temp].u=w;

    edge[temp].len=c;

    edge[temp].next=head[v];

    head[v]=temp;

    temp++;

}

int main()

{

    scanf("%d",&T);

    while(T--)

    {

        temp=0;

        scanf("%d%d",&n,&m);

        memset(head,-1,sizeof(head));

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

        {

            int v,w,c;

            scanf("%d%d%d",&v,&w,&c);

            addEdge(v,w,c);

        }

        scanf("%d%d",&s,&t);

        int ans=Dijstra(s,t);

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

    }

    return 0;

}

巴特西

poj3463 最短路和比最短路长1的路径数

最新文章

热门文章