程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj-3463-Sightseeing-求次短路

poj-3463-Sightseeing-求次短路

編輯：C++入門知識

題意是求最短路的數量和比最短路長1的路的數量。

此題的本質就是在dij的過程中，可以把一個點走兩次。一次最短，一次次短。

最後判斷即可。

#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define maxn 210000
#define maxeg 22000
#define maxpt 2001
#define INF 99999999
struct G
{
    int num;
    int head[maxpt];
    struct list{int u,v,w,next;}edge[maxeg];
    void init(){
        memset(head,-1,sizeof(head));
        num=0;
    }
    void add(int u,int v,int w){
        edge[num].u=u;edge[num].v=v;edge[num].w=w;
        edge[num].next=head[u];head[u]=num++;
    }
}gra,fgra;
int n,m;
//priority_queueque;
void dij(int x,int y)
{
    int i;
    int dis[maxpt][2];
    int vis[maxpt][2];
    int num[maxpt][2];
    for(i=0;i<=n;i++)
    {
        dis[i][0]=dis[i][1]=INF;
        vis[i][0]=vis[i][1]=0;
        num[i][0]=num[i][1]=0;
    }
    dis[x][0]=0;
    num[x][0]=1;
    while(1)
    {
        int minn=INF;
        int ip;
        int leap;
        for(i=1;i<=n;i++)
        {
            if(!vis[i][0])
            {
                if(minn>dis[i][0])
                {
                    minn=dis[i][0];
                    ip=i;leap=0;
                }
            }
            if(!vis[i][1])
            {
                if(minn>dis[i][1])
                {
                    minn=dis[i][1];
                    ip=i;leap=1;
                }
            }
        }
        if(minn==INF)break;
        vis[ip][leap]=1;
        //cout<=dis[ip][leap]+w)
            {
                if(dis[v][0]==dis[ip][leap]+w)num[v][0]+=num[ip][leap];
                else
                {
                    dis[v][1]=dis[v][0];
                    num[v][1]=num[v][0];
                    dis[v][0]=dis[ip][leap]+w;num[v][0]=num[ip][leap];
                }
            }
            else if(!vis[v][1]&&dis[v][1]>=dis[ip][leap]+w)
            {
                if(dis[v][1]==dis[ip][leap]+w)num[v][1]+=num[ip][leap];
                else
                {
                    dis[v][1]=dis[ip][leap]+w;num[v][1]=num[ip][leap];
                }
            }
        }
    }
    int ans=0;
    if(dis[y][0]==dis[y][1]-1)
    {
        ans=num[y][0]+num[y][1];
    }
    else ans=num[y][0];
    cout<