题目大意：求两点间最短路与长度为最短路长度+1的路径的条数之和。

方法1：最短路径+DP

首先求出ST间最短路径，然后根据递归式记忆化搜索（因此还要构造反向图）。

我们知道到达终点的路径长度最长为maxDist(T)=minDist(T)+1，而与终点相连的节点的路径长度最长为maxDist(T)-Weight(e)。这些节点与更前面的节点也是如此。于是我们从终点开始递归，利用PathCnt(v)=sum(PathCnt(u)) (PathCnt(u)=|{Dist(u)|Dist(u)<=maxDist(u)}|)。

初值注意不能直接PathCnt(S)设为1，因为S点也可能在一个环内。因此我们应当建点S'->S，边权为0。

代码：

#include
#include
#include
using namespace std;

#define LOOP(i,n) for(int i=1; i<=n; i++)
const int MAX_NODE = 1010, MAX_EDGE = 10010 * 2, INF = 0x3f3f3f3f;

struct Node;
struct Edge;

struct Node
{
int Id, Dist, PathCnt[2];
bool Inq;
Edge *Head, *RevHead;
}_nodes[MAX_NODE], *Start, *Target;
int _vCount;

struct Edge
{
int Weight;
Node *From, *To;
Edge *Next;
}*_edges[MAX_EDGE];
int _eCount;

void Init(int vCount)
{
_vCount = vCount;
_eCount = 0;
memset(_nodes, 0, sizeof(_nodes));
}

void SetST(int sId, int tId)
{
Start = sId + _nodes;
Target = tId + _nodes;
}

Edge *NewEdge()
{
_eCount++;
return _edges[_eCount] ? _edges[_eCount] : _edges[_eCount] = new Edge();
}

void AddEdge(Node *from, Node *to, int weight, bool IsRev)
{
Edge *e = NewEdge();
e->From = from;
e->To = to;
e->Weight = weight;
Edge *&head = IsRev ? from->RevHead : from->Head;
e->Next = head;
head = e;
}

void Build(int uId, int vId, int weight)
{
Node *from = uId + _nodes, *to = vId + _nodes;
from->Id = uId;
to->Id = vId;
AddEdge(from, to, weight, false);
AddEdge(to, from, weight, true);
}

void SPFA()
{
static queue q;
LOOP(i, _vCount)
{
_nodes[i].Dist = INF;
_nodes[i].Inq = false;
}
Start->Dist = 0;
Start->Inq = true;
q.push(Start);
while (!q.empty())
{
Node *u = q.front();
q.pop();
u->Inq = false;
for (Edge *e = u->Head; e; e = e->Next)
{
if (u->Dist + e->Weight < e->To->Dist)
{
e->To->Dist = u->Dist + e->Weight;
if (!e->To->Inq)
{
e->To->Inq = true;
q.push(e->To);
}
}
}
}
}

int CntPath(Node *cur, int maxDist)
{
if (cur->Dist > maxDist)
return 0;
int &pathCnt = cur->PathCnt[maxDist - cur->Dist];
if (pathCnt != -1)
return pathCnt;
if (cur == Start)
return 1;
pathCnt = 0;
for (Edge *e = cur->RevHead; e; e = e->Next)
pathCnt += CntPath(e->To, maxDist - e->Weight);
return pathCnt;
}

int main()
{
#ifdef _DEBUG
freopen("c:\\noi\\source\\input.txt", "r", stdin);
#endif
int testCase, totNode, totEdge, uId, vId, weight, sId, tId;
scanf("%d", &testCase);
while (testCase--)
{
scanf("%d%d", &totNode, &totEdge);
Init(totNode + 1);
LOOP(i, totEdge)
{
scanf("%d%d%d", &uId, &vId, &weight);
Build(uId, vId, weight);
}
scanf("%d%d", &sId, &tId);
Build(totNode + 1, sId, 0);
SetST(totNode + 1, tId);
SPFA();
LOOP(i, _vCount)
_nodes[i].PathCnt[0] = _nodes[i].PathCnt[1] = -1;
printf("%d\n", CntPath(Target, Target->Dist + 1));
}
return 0;
}

方法2：Dijkstra

同时更新一个节点的最短路径长度和次短路长度以及它们的个数。优先队列里维护节点，key值为节点最短路长度或次短路长度。究竟是哪个长度我们不用管它，该节点能更新最短路就更新最短路，否则看看能不能更新次短路。

注意：1.如果v的newDist与v原来的路径长度相等，更新完路径个数后不要入队！队列只维护最短路径或次短路径。2.更新完了v最短路，v次短路也更新了，所以要把v节点以key值为最短路长度和次短路长度入队两次。3.优先队列是大根堆。

代码：

#include
#include
#include
#include
using namespace std;

#define LOOP(i,n) for(int i=1; i<=n; i++)
#define _1st 0
#define _2nd 1
const int MAX_NODE = 1010, MAX_EDGE = 10010 * 2, INF = 0x3f3f3f3f;

struct Node;
struct Edge;

struct Node
{
int Id, Dist[2], Cnt[2];
bool Done[2];
Edge *Head;
}_nodes[MAX_NODE], *Start, *Target;
int _vCount;

struct Edge
{
int Weight;
Node *From, *To;
Edge *Next;
}*_edges[MAX_EDGE];
int _eCount;

struct HeapNode
{
Node *Org;
int Dist;
bool Is2nd;
bool operator <(const HeapNode a)const { return Dist > a.Dist; }
HeapNode(Node *a, bool isSec):Org(a),Dist(a->Dist[isSec]),Is2nd(isSec){}
};

void Init(int vCount)
{
memset(_nodes, 0, sizeof(_nodes));
_vCount = vCount;
_eCount = 0;
}

void SetST(int sId, int tId)
{
Start = sId + _nodes;
Target = tId + _nodes;
}

Edge *NewEdge()
{
_eCount++;
if (_edges[_eCount])
return _edges[_eCount];
else
return _edges[_eCount] = new Edge();
}

Edge *AddEdge(Node *from, Node *to, int weight)
{
Edge *e = NewEdge();
e->From = from;
e->To = to;
e->Weight = weight;
e->Next = e->From->Head;
e->From->Head = e;
return e;
}

void Build(int uId, int vId, int weight)
{
Node *u = uId + _nodes, *v = vId + _nodes;
u->Id = uId;
v->Id = vId;
AddEdge(u, v, weight);
}

void Dijkstra()
{
static priority_queue q;
LOOP(i, _vCount)
{
_nodes[i].Dist[0] = _nodes[i].Dist[1] = INF;
_nodes[i].Done[0] = _nodes[i].Done[1] = false;
}
Start->Dist[_1st] = 0;
Start->Cnt[_1st] = 1;
q.push(HeapNode(Start, false));
while (!q.empty())
{
HeapNode cur = q.top();
q.pop();
Node *u = cur.Org;
if (u->Done[cur.Is2nd])
continue;
u->Done[cur.Is2nd] = true;
for (Edge *e = u->Head; e; e = e->Next)
{
int newDist = cur.Dist + e->Weight;
if (newDist < e->To->Dist[_1st])
{
e->To->Cnt[_2nd] = e->To->Cnt[_1st];
e->To->Dist[_2nd] = e->To->Dist[_1st];
e->To->Cnt[_1st] = u->Cnt[cur.Is2nd];
e->To->Dist[_1st] = newDist;
q.push(HeapNode(e->To, _1st));
q.push(HeapNode(e->To, _2nd));
}
else if (newDist > e->To->Dist[_1st] && newDist < e->To->Dist[_2nd])
{
e->To->Cnt[_2nd] = u->Cnt[cur.Is2nd];
e->To->Dist[_2nd] = newDist;
q.push(HeapNode(e->To, _2nd));
}
else if (newDist == e->To->Dist[_1st])
e->To->Cnt[_1st] += u->Cnt[cur.Is2nd];
else if (newDist == e->To->Dist[_2nd])
e->To->Cnt[_2nd] += u->Cnt[cur.Is2nd];
}
}
}

int main()
{
#ifdef _DEBUG
freopen("c:\\noi\\source\\input.txt", "r", stdin);
freopen("c:\\noi\\source\\output.txt", "w", stdout);
#endif
int testCase, totNode, totEdge, uId, vId, weight, sId, tId;
scanf("%d", &testCase);
while (testCase--)
{
scanf("%d%d", &totNode, &totEdge);
Init(totNode);
LOOP(i, totEdge)
{
scanf("%d%d%d", &uId, &vId, &weight);
Build(uId, vId, weight);
}
scanf("%d%d", &sId, &tId);
SetST(sId, tId);
Dijkstra();
printf("%d\n", Target->Cnt[_1st] + ((Target->Dist[_2nd] == Target->Dist[_1st] + 1) ? Target->Cnt[_2nd] : 0));
}
return 0;
}

　　错误做法：SPFA同时更新最短路和次短路。

为什么Dijkstra就可以？因为u出队时，由于Dijkstra的贪心，u本身就更新完了，无后顾之忧；而SPFA中，u还没更新完就要往下更新。u往下更新以后，如果以后运算过程中u自己再被更新，此时再由u往下更新v，v节点就错了。