求出家到其他点的最短路径，题目的条件变成了u->v不是回头路等价于d[u]>d[v]。

然后根据这个条件建DAG图，跑dp统计方案数，dp[u] = sum(dp[v])。

#include
     
      using namespace std;const int maxn = 1001, maxm = 2002;struct Edge{    int v,w,nxt;};#define PB push_backvector
      
        edges;vector
       
         G[maxn];int head[maxn];int d[maxn];void addEdge(int u,int v,int w){    edges.PB({v,w,head[u]});    head[u] = edges.size()-1;}void init(){    memset(head,-1,sizeof(head));    edges.clear();}typedef pair
        
          Node;#define fi first#define se secondvoid dijkstra(int s = 1){    memset(d,0x3f,sizeof(d));    priority_queue
         
          
           ,greater
           
             > q; q.push(Node(d[s] = 0,s)); while(q.size()){ Node x = q.top(); q.pop(); int u = x.se; if(x.fi != d[u]) continue; for(int i = head[u]; ~i ; i = edges[i].nxt){ Edge &e = edges[i]; if(d[e.v] > d[u]+e.w){ d[e.v] = d[u]+e.w; q.push(Node(d[e.v],e.v)); } } }}int dp[maxn];int dfs(int u){ int &ans = dp[u]; if(~ans) return ans; if(u == 1) return ans = 1; ans = 0; for(int i = 0; i < (int)G[u].size(); i++){ ans += dfs(G[u][i]); } return ans;}void rebuild(int n){ for(int i = 0; i < n; i++) G[i].clear(); for(int u = 0; u < n; u++){ for(int i = head[u]; ~i; i = edges[i].nxt){ int v = edges[i].v; if(d[v] < d[u]) G[u].PB(v); } }}int main(){ //freopen("in.txt","r",stdin); int n,m; while(scanf("%d%d",&n,&m),n){ init(); while(m--){ int u,v,w; scanf("%d%d%d",&u,&v,&w); u--;v--; addEdge(u,v,w); addEdge(v,u,w); } dijkstra(); rebuild(n); memset(dp,-1,sizeof(dp)); printf("%d\n",dfs(0)); } return 0;}