题目描述：给你一个有向图，边权告诉你，求从s点到t点的最短路和比最短路大1的路径的数目。（两条路只要有一条边不同，这两条路就认为是不同的）。

解题报告：

Dij的性质：每找到第一个dis最小的点就是这个点的答案。

同理应用到次短路上，dis[i][0]表示到i的最短路长度，dis[i][1]表示到i的次短路长度

num[i][0]最短路数目，num[i][1]次短路数目。

算法如下：

if(x<最小)更新最小，次小

else if(==最小)更新方法数

else if(x<次小)更新次小

else if(x==次小)更新方法数

代码如下：

#include<iostream>

#include<queue>

using namespace std;

struct edge{int to, val, next;}e[10001];

int v[1200], cnt, d[1200][2], num[1200][2]; bool vst[1200][2];

void insert(int from, int to, int val)

{

    e[cnt].val = val, e[cnt].to = to, e[cnt].next = v[from]; v[from] = cnt++;

}

struct jeo

{

    int id, flag;

    jeo(int id, int flag): id(id), flag(flag){}

    friend bool operator < (jeo a, jeo b){return d[a.id][a.flag] > d[b.id][b.flag];}

};

int dij(int n, int from, int to)

{

    for(int i = 1; i <= n; i++)

        num[i][0] = num[i][1] = vst[i][0] = vst[i][1] = 0, d[i][0] = d[i][1] = 0x7fffffff;

    priority_queue<jeo> heap;

    d[from][0] = 0; heap.push(jeo(from, 0)); num[from][0] = 1;

    while(!heap.empty())

    {

        jeo tmp = heap.top(); heap.pop();

        if (vst[tmp.id][tmp.flag]) continue;

        vst[tmp.id][tmp.flag] = 1;

        for(int i = v[tmp.id]; i != -1; i = e[i].next)

        {

            int val = d[tmp.id][tmp.flag] + e[i].val;

            if (val < d[e[i].to][0])

            {

                if (d[e[i].to][0] != 0x7fffffff)

                {

                    d[e[i].to][1] = d[e[i].to][0];

                    num[e[i].to][1] = num[e[i].to][0];

                    heap.push(jeo(e[i].to, 1));

                }

                d[e[i].to][0] = val, num[e[i].to][0] = num[tmp.id][tmp.flag];

                heap.push(jeo(e[i].to, 0));

            }

            else if (val == d[e[i].to][0]) num[e[i].to][0] += num[tmp.id][tmp.flag];

            else if (val < d[e[i].to][1])

            {

                d[e[i].to][1] = val, num[e[i].to][1] = num[tmp.id][tmp.flag];

                heap.push(jeo(e[i].to, 1));

            }

            else if (val == d[e[i].to][1]) num[e[i].to][1] += num[tmp.id][tmp.flag];

        }

    }

    if (d[to][1] - d[to][0] == 1) num[to][0] += num[to][1];

    return num[to][0];

}

int t, n, m, from, to, val;

int main()

{

    scanf("%d", &t);

    while(t--)

    {

        scanf("%d%d", &n, &m); memset(v, -1, sizeof(int) * (n + 1)); cnt = 0;

        while(m-- && scanf("%d%d%d", &from, &to, &val)) insert(from, to, val);

        scanf("%d%d", &from, &to);

        printf("%d\n", dij(n, from, to));

    }

    return 0;

}