题目链接：https://vjudge.net/problem/UVA-10917
题目意思：Jimmy下班回家要闯过一下森林，劳累一天后在森林中散步是非常惬意的事，所以他打算每天沿着一条不同的路径回家，欣赏不同的风景，但他也不太想太晚回家，因此他不打算走回头路。换句话来说，他只会沿着如下条件的道路(A,B)走：存在一条从B出发回家的路径，比所有从A出发回家的路径都要短。我们的任务是要找出一共有有多少条不同的回家路径，家的编号是2，公司的编号是1。
题目思路：最短路+dp，我们现在考虑如何dp，由于从B回家的路比所有从A回家的路都短，所以如果从2出发跑一遍最短路，如果我们重新建一个图了话，如果原图中存在边，且dist[A]>dist[B]的两个AB之间需要建一条边。现在我们dp，考虑子结构，从x点回家的所有路径是多少？应该是点x的边集中所有dist[y]>dist[x]的点y，回家路径的和。也就说当这些y的回家路径确定了以后x回家的路径的数量才确定。所以我们实际上是跑以2为起点的最短路，以2为起点开始的dfs。直接看代码吧！
代码：
//Author: xiaowuga
#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX INT_MAX
#define mem(s,ch) memset(s,ch,sizeof(s))
const long long N=;
const long long mod=1e9+;
typedef long long LL;
typedef int II;
typedef unsigned long long ull;
#define nc cout<<"nc"<<endl
#define sp " "
II n,m;
vector<pair<II,II> >G[N];
II d[N];
II path[N],done[N];
void Dijkstra(II s,II t){
II vis[N];
mem(d,inf);mem(vis,);
d[s]=;
priority_queue<pair<II,II> >Q;
Q.push(make_pair(-d[s],s));//由于优先队列默认是大顶堆，我们直接放入一个负数就可以了。
while(!Q.empty()){
II now=Q.top().second;
Q.pop();
if(vis[now]) continue;
vis[now]=;
for(II i=;i<G[now].size();i++){
II v=G[now][i].first,w=G[now][i].second;
if(d[v]>d[now]+w){
d[v]=d[now]+w;
Q.push(make_pair(-d[v],v));
}
}
}
}
II dfs(II u){
if(path[u]!=-) return path[u];
path[u]=;
for(II i=;i<G[u].size();i++){
II v=G[u][i].first;
if(d[u]<d[v]){
path[u]+=dfs(v);
}
}
return path[u];
}
int main() {
ios::sync_with_stdio(false);cin.tie();
while(cin>>n&&n){
cin>>m;
for(II i=;i<=n;i++) G[i].clear();
for(II i=;i<m;i++){
II a,b,d;
cin>>a>>b>>d;
G[a].push_back(make_pair(b,d));
G[b].push_back(make_pair(a,d));
}
Dijkstra(,);
//for(II i=1;i<=n;i++) cout<<d[i]<<' '; cout<<endl;
mem(path,-);path[]=;
II ans=dfs();
cout<<ans<<endl;
}
return ;
}