题意：看样子很多人都把这题目看错了，以为是求最短路的条数。真正的意思是：假设 A和B 是相连的，当前在 A 处，
如果 A 到终点的最短距离大于 B 到终点的最短距离，则可以从 A 通往 B 处，问满足这种的条件的从办公室到家的路径条数。
分析:1、以终点 2 为起点 Dijkstra跑一边最短路，找到所有点到2的最短距离；
2、直接DFS记忆化搜索。
注意:记忆化搜索时的return值，否则此很容易TLE
解法1:O(n^2)
#include<iostream>
#include<cstdio>
#include<cstring>
#define inf 0x7fffffff
int n,m,u,v,w;
using namespace std;
int g[][],dis[];
int vis[],path[];
void Dijkstra(int u)
{
memset(vis,,sizeof(vis));
for(int i=;i<=n;i++)
dis[i]=g[u][i];
dis[u]=;
vis[u]=;
for(int i=;i<=n;i++){
int k,min=inf;
for(int j=;j<=n;j++){
if(!vis[j]&&min>dis[j]){
min=dis[j];
k=j;
}
}
vis[k]=;
for(int j=;j<=n;j++){
if(!vis[j]&&g[k][j]!=inf){//g[k][j]!=inf不能少
if(dis[j]>dis[k]+g[k][j])
dis[j]=dis[k]+g[k][j];
}
}
}
} int dfs(int u)
{
if(path[u]!=-) return path[u];
if(u==) return ;//记忆化搜索，如果该点已经访问过了，就返回从该点到终点的路径数
int num=;
for(int v=;v<=n;v++){
if(g[u][v]!=inf&&dis[v]<dis[u])
num+=dfs(v);
}
path[u]=num;//不能直接return num,否则会TLE
return path[u];
} int main()
{
while(scanf("%d",&n),n){
scanf("%d",&m);
memset(path,-,sizeof(path));
for(int i=;i<=n;i++){
for(int j=;j<=n;j++)
g[i][j]=(i==j?:inf);
}
for(int i=;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
if(g[u][v]>w)//处理重边
g[u][v]=g[v][u]=w;
}
Dijkstra();
cout<<dfs()<<endl;
}
return ;
}
解法2:刚开始dfs中TLE,修改后就一直WA...至今缘由不明，还是太菜了
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#define inf 0x7fffffff
using namespace std;
struct Node
{
int u,d;
Node(long long uu,long long dd){
u=uu,d=dd;
}
friend bool operator < (Node a,Node b){
return a.d>b.d;
}
};
struct Edge
{
int v,w;
Edge(long long vv,long long ww){
v=vv,w=ww;
}
};
bool vis[];
long long path[];
vector<Edge> g[];//为Edge类型
priority_queue<Node>que;//为Node类型
long long dis[];
void Dijkstra()
{
dis[]=;
que.push(Node(,));
while(!que.empty()){
Node p=que.top();
que.pop();
long long u=p.u;
if(!vis[u]){
vis[u]=;//vis[u]=1位置不能放错
for(int i=;i<g[u].size();i++){
long long v=g[u][i].v;
long long c=g[u][i].w;
if(!vis[v]){//这里不能写vis[v]=1;
if(dis[v]>dis[u]+c){
dis[v]=dis[u]+c;
que.push(Node(v,dis[v]));
}
}
}
}
}
}
int dfs(int u)
{
if(path[u]!=-) return path[u];
if(u==) return ;//找到终点，返回1条路
long long num=;//注意num的位置
for(int i=;i<g[u].size();i++){
int v=g[u][i].v;
if(dis[v]<dis[u])
num+=dfs(v);
}
path[u]=num;
return path[u];//返回从u到终点的所有路径数
}
int main()
{
long long n,m,u,v,w;
while(scanf("%lld",&n),n){
scanf("%lld",&m);
memset(g,,sizeof(g));//切记清零
memset(vis,,sizeof(vis));
for(int i=;i<=n;i++) dis[i]=inf;
for(int i=;i<=m;i++){
scanf("%lld%lld%lld",&u,&v,&w);
g[u].push_back(Edge(v,w));
g[v].push_back(Edge(u,w));
}
Dijkstra();
memset(path,-,sizeof(path));//初始化
printf("%lld\n",dfs());
}
}