原先一直在做一道省赛题，由于题意错误理解成球最短路条数，误打误撞敲了最短路条数，又发现hdu3599（多校）求边不可重复最短路条数。下面说说俩种问题解法：

最短路条数：

         求一个图一共一几条最短路径，思路：先从终点跑一边最短路，记录终点到到所有点最短距离（d【i】），然后从起点出发，dfs 按d[i]走（必是最短路径），一句话：我到终点的最短路条数=我的所有孩子到终点的最短路条数之和，这样只需一遍即可。这不知道是不是叫记忆化搜索？

边不可重复最短路径条数：（最短路+建新图之最大流）

       hdu3599题意：求1-->n最短路条数，所有路径边不可重复。思路：边不可重复？？！！转为流量的为1 的话，求最大流啊（以后切记该方法，不可重复问题转最大流）！于是：先跑一遍最短路（随便从起点还是终点）,然后按老图中是最短路的边就在新图添加一条边，权为1，这样的话，从起点到终点跑最大流即为答案。

 附代码：问题一：

#include
    
     #include
     
      #include
      
       using namespace std;int n;int e[100000][3];int head[2000];int nume=0;int d[2000];const int inf =0x3f3f3f3f;int vis[2000];int inq[2000];void adde(int a,int b,int w){    e[nume][0]=b;e[nume][1]=head[a];head[a]=nume;    e[nume++][2]=w;    e[nume][0]=a;e[nume][1]=head[b];head[b]=nume;    e[nume++][2]=w;}void spfa()              //一遍求出终点到所有点的最短路长度d[i]。{    queue
       
        q;    int start;    start=n;    inq[start]=1;    q.push(start);    d[start]=0;    while(!q.empty())    {        int cur=q.front();       q.pop();       inq[cur]=0;       for(int i=head[cur];i!=-1;i=e[i][1])       {           int v=e[i][0];          if(d[cur]+e[i][2]
        
         >ta;    while(ta--)    {          scanf("%d",&n);          int aa,bb,cc;           for(int i=0;i<=n;i++)            {                head[i]=-1;                nowd[i]=d[i]=inf;               inq[i]=counted[i]=vis[i]=0;             }            nume=0;       while(~scanf("%d%d%d",&aa,&bb,&cc)&&(aa||bb||cc))             adde(aa,bb,cc);         spfa();        counted[n]=1;        nowd[1]=0;        vis[1]=1;       cout<
         
          <
         
        
       
      
     
    

问题2：

#include
    
     #include
     
      #include
      
       using namespace std;int n;int e[2260000][3];int head[1510];int nume=0;int d[1510];const int inf =0x3f3f3f3f;int inq[1510];void adde(int a,int b,int w)   //原图{    e[nume][0]=b;e[nume][1]=head[a];head[a]=nume;    e[nume++][2]=w;    e[nume][0]=a;e[nume][1]=head[b];head[b]=nume;    e[nume++][2]=w;}int ee[2260000][3];int head2[1510];     //新图void adde2(int a,int b){    ee[nume][0]=b;ee[nume][1]=head2[a];head2[a]=nume;    ee[nume++][2]=1;    ee[nume][0]=a;ee[nume][1]=head2[b];head2[b]=nume;    ee[nume++][2]=0;}void spfa()              //求出终点到所有点的最短路长度d[i]。{    queue
       
        q;    int start;    start=n;    inq[start]=1;    q.push(start);    d[start]=0;    while(!q.empty())    {        int cur=q.front();       q.pop();       inq[cur]=0;       for(int i=head[cur];i!=-1;i=e[i][1])       {           int v=e[i][0];          if(d[cur]+e[i][2]