题目：Walk Through the Forest
题意：给出一张有向图，问从1走到2有多少种不同的路径，使经过的每一条有向边A->B均满足dist[A]<dist[B]（dist[]为1到这些点的最短路）。
思路：先用dijkstra求最短路，然后在所有满足dist[A]<dist[B]的两点之间连上一条边，用dp求解。
注意：
1、priority_queue是大根堆，定义<运算符时不能定反。
2、对于dist[A]<dist[B]的两点，并同时满足存在一条A->B的边，才能在这两点之间连边。
3、由于用的是记忆化搜索，所以用于记忆化的f[]不能忘记初始化。
4、状态转移方程不能弄错。
代码：
#include<bits/stdc++.h>
using namespace std;#define maxn 1000struct Pair {int x;int y;Pair(int xx=0,int yy=0) {x=xx,y=yy;}bool operator < (const Pair& oth) const {return x>oth.x||(x==oth.x&&y<oth.y);}
};int n,m;vector<Pair> a[maxn+5];
int dist[maxn+5];vector<int> g[maxn+5];
int f[maxn+5];void make_g() {for(int i=1; i<=n; i++) {for(int j=0;j<a[i].size();j++){if(dist[a[i][j].x]<dist[i]){g[i].push_back(a[i][j].x);}}}
}void dijkstra() {priority_queue<Pair> p;bool c[maxn+5]= {0};p.push(Pair(0,2));while(!p.empty()) {Pair x=p.top();p.pop();if(c[x.y]) continue;c[x.y]=true;for(int i=0; i<a[x.y].size(); i++) {if(dist[a[x.y][i].x]>x.x+a[x.y][i].y) {dist[a[x.y][i].x]=x.x+a[x.y][i].y;p.push(Pair(dist[a[x.y][i].x],a[x.y][i].x));}}}
}void init() {for(int i=1; i<=maxn; i++) a[i].clear(),g[i].clear();for(int i=1; i<=maxn; i++) dist[i]=1000000000;dist[2]=0;memset(f,0,sizeof(f));
}void readin() {scanf("%d",&m);for(int i=1; i<=m; i++) {int x,y,z;scanf("%d%d%d",&x,&y,&z);a[x].push_back(Pair(y,z));a[y].push_back(Pair(x,z));}
}void dp(int x) {if(x==2) {f[x]=1;return ;}f[x]=0;for(int i=0;i<g[x].size();i++){if(!f[g[x][i]]) dp(g[x][i]);f[x]+=f[g[x][i]];}
}int main() {while(~scanf("%d",&n)&&n) {init();readin();dijkstra();make_g();dp(1);printf("%d\n",f[1]);}return 0;
}