poj-3463-Sightseeing-求次短路

题意是求最短路的数量和比最短路长1的路的数量。

此题的本质就是在dij的过程中，可以把一个点走两次。一次最短，一次次短。

最后判断即可。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
#include<map>
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_queue<list>que;
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<<ip<<" "<<leap<<" "<<minn<<endl;
        for(i=gra.head[ip];i!=-1;i=gra.edge[i].next)
        {
            int v=gra.edge[i].v;
            int w=gra.edge[i].w;
           // cout<<v<<" "<<w<<endl;
            if(!vis[v][0]&&dis[v][0]>=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<<ans<<endl;
}
int main()
{
    int i,a,b,c,s,t,k;
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        gra.init();
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            gra.add(a,b,c);
        }
        scanf("%d%d",&s,&t);
        dij(s,t);
    }
    return 0;
}

poj-3463-Sightseeing-求次短路,布布扣,bubuko.com

poj-3463-Sightseeing-求次短路

原文：http://blog.csdn.net/rowanhaoa/article/details/22694727