POJ 3463 Sightseeing

Description

已知一张图（单向边），起点S和终点F，求从S到F的最短路和比最短路长1的路径的条数之和。

如果路径A和B有至少一个点不相同，那么A和B就是两条不同路径。

例如，在上图中， S = 1 , F = 5:路径 1 → 2 → 5 和 1 → 3 → 5 是最短路，长度都为 6. 有一条比最短路长1单位的路径 1 → 3 → 4 → 5, 路径长为 7.

Input

多样例。

第一行是样例的个数t。

对于每个样例：

• 第一行两个整数 N ,M,  2 ≤ N ≤ 1,000 , 1 ≤ M ≤ 10, 000:图的点数和边数。

• 接下来M行，每行3个整数 A, B, L, 1 ≤ A, B ≤ N, A ≠ B , 1 ≤ L ≤ 1,000, 表示一条从A点到B点，长度为L的单向边。

  通过这条边只能由A走到B，不能反着走。

  不过，可以存在其他B，A，L的边可以由B走到A。

• 接下来两个整数S和F，表示起点和终点， 1 ≤ S, F ≤ N , S ≠ F: 从S到F保证存在至少一条路径。

第一个样例对应题中的图。

Output

对每个样例，输出一行一个整数，表示最短路和比最短路长1的路径条数之和，样例保证答案不超过10的9次方。

Sample Input

25 8
1 2 3
1 3 2
1 4 5
2 3 1
2 5 3
3 4 2
3 5 4
4 5 3
1 5
5 6
2 3 1
3 2 1
3 1 10
4 5 2
5 2 7
5 2 7
4 1      

Sample Output

32

求个最短路条数和次短路条数

#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=2005;
const int INF=0x7FFFFFFF;
int T,D[maxn][2],x,y,z,f[maxn][2],n,m,F[maxn][2];

struct point
{
    int x,y;
    point(){}
    point(int x,int y):x(x),y(y){}
};
vector<point> dis[maxn];

int find_dis(int x,int y)
{
    memset(f,0,sizeof(f));
    memset(F,0,sizeof(F));
    memset(D,-1,sizeof(D));
    D[x][0]=0;  F[x][0]=1;  
    for (int i=1;i<=n+n;i++)
    {
        int now=-1,flag=-1;
        for (int j=1;j<=n;j++)
            if (D[j][0]>=0&&!f[j][0]) 
            {
                if (now<0) now=j,flag=0;
                if (D[j][0]<D[now][0]) now=j,flag=0;
            }
        for (int j=1;j<=n;j++)
            if (D[j][1]>=0&&!f[j][1]) 
            {
                if (now<0) now=j,flag=1;
                if (D[j][1]<D[now][flag]) now=j,flag=1;
            }
        if (flag<0) break;
        f[now][flag]=1;
        for (int j=0;j<dis[now].size();j++)
        {
            int v=dis[now][j].x;
            int u=dis[now][j].y+D[now][flag];
            if (D[v][0]<0||D[v][0]>u)
            {
                D[v][1]=D[v][0]; D[v][0]=u;
                F[v][1]=F[v][0]; F[v][0]=F[now][0];
            }
            else if (D[v][0]==u) F[v][0]+=F[now][flag];
            else if (D[v][1]==u) F[v][1]+=F[now][flag];
            else if (D[v][1]<0||D[v][1]>u) F[v][1]=F[now][flag],D[v][1]=u;
        }
    }
    if (D[y][1]==D[y][0]+1) return F[y][0]+F[y][1];
    else return F[y][0];
}

int main()
{
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%d",&n,&m);
        for (int i=1;i<=n;i++) dis[i].clear();
        for(int i=1;i<=m;i++) 
       {
           scanf("%d%d%d",&x,&y,&z);
           dis[x].push_back(point(y,z));
       }
        scanf("%d%d",&x,&y);
        printf("%d\n",find_dis(x,y));
    }
    return 0;
}