题目给一张有向图，问从起点1到终点2沿着合法的路走有种走法，合法的路指从u到v的路，v到终点的距离严格小于u到终点的距离。
先SPFA预处理出所有合法的路，然后这些路肯定形成一个DAG，然后DP一下就OK了，d[u]表示u到终点2的方案数。
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define INF (1LL<<60)
#define MAXN 1111
#define MAXM 1111*1111 struct Edge{
int u,v,w,next;
}edge[MAXM];
int NE,head[MAXN];
void addEdge(int u,int v,int w){
edge[NE].u=u; edge[NE].v=v; edge[NE].w=w;
edge[NE].next=head[u]; head[u]=NE++;
} int n;
long long dist[MAXN];
void SPFA(){
for(int i=; i<=n; ++i) dist[i]=INF;
dist[]=;
bool vis[MAXN]={};
vis[]=;
queue<int> que;
que.push();
while(!que.empty()){
int u=que.front(); que.pop();
for(int i=head[u]; i!=-; i=edge[i].next){
int v=edge[i].v;
if(dist[v]>dist[u]+edge[i].w){
dist[v]=dist[u]+edge[i].w;
if(!vis[v]){
vis[v]=;
que.push(v);
}
}
}
vis[u]=;
}
} int d[MAXN];
int dfs(int u){
if(u==) return ;
if(d[u]!=-) return d[u];
int res=;
for(int i=head[u]; i!=-; i=edge[i].next){
int v=edge[i].v;
res+=dfs(v);
}
return d[u]=res;
}
int main(){
int m,a,b,c;
while(~scanf("%d",&n) && n){
scanf("%d",&m);
NE=;
memset(head,-,sizeof(head));
while(m--){
scanf("%d%d%d",&a,&b,&c);
addEdge(a,b,c); addEdge(b,a,c);
}
SPFA();
int tmp=NE; NE=;
memset(head,-,sizeof(head));
for(int i=; i<tmp; ++i){
int u=edge[i].u,v=edge[i].v;
if(dist[u]>dist[v]) addEdge(u,v,);
}
memset(d,-,sizeof(d));
printf("%d\n",dfs());
}
return ;
}