UVA 10917 Walk Through the Forest（dijkstra+DAG上的dp）

用新模板阿姨了一天，换成原来的一遍就ac了= =

题意很重要。。最关键的一句话是说:若走A->B这条边，必然是d[B]<d[A]，d[]数组保存的是各点到终点的最短路。

所以先做dij，由d[B]<d[A]可知，所走的路径上各点的d[]值是由大到小的，即是一个DAG，从而决定用记忆化搜索查找总的路径数。

 #include<stdio.h>

 #include<string.h>

 #include<algorithm>

 using namespace std;

 const int MAXN=;

 const int INF =0x0fffff;

 int G[MAXN][MAXN],vis[MAXN],d[MAXN],n;

 int mark[MAXN],dp[MAXN];

 void dij(int n)

 {

     memset(vis,,sizeof(vis));

     for(int i=;i<=n;i++)

         if(i==)d[i]=;

         else d[i]=INF;

     for(int i=;i<n;i++)

     {

         int x,m=INF;

         for(int y=;y<=n;y++)

         if(!vis[y]&&d[y]<m){

             x=y;

             m=d[x];

         }

         vis[x]=;

         for(int y=;y<=n;y++)

             if(d[y]>d[x]+G[x][y])

                 d[y]=d[x]+G[x][y];

     }

 }

 int dfs(int u,int ed)

 {

     if(mark[u])

         return dp[u];

     mark[u]=;

     if(u==ed){

         dp[u]=;

         return dp[u];

     }

     int ans=;

     for(int i=;i<=n;i++)

     {

         if(G[u][i]!=INF&&d[i]<d[u])

             ans+=dfs(i,ed);

     }

     dp[u]=ans;

     return dp[u];

 }

 int main()

 {

     int m,u,v,c;

     while(~scanf("%d",&n))

     {

         if(!n)

             return ;

         scanf("%d",&m);

         for(int i=;i<=n;i++)

             for(int j=;j<=n;j++)

                 if(i==j)G[i][j]=;

                 else G[i][j]=INF;

         for(int i=;i<m;i++)

         {

             scanf("%d%d%d",&u,&v,&c);

             if(G[u][v]>c)

                 G[u][v]=G[v][u]=c;

         }

         dij(n);

         memset(mark,,sizeof(mark));

         printf("%d\n",dfs(,));

     }

     return ;

 }

后记：

回顾这道题，想到了一个问题：两点之间可以存在重边，用邻接表存储，同一条路线会被重复计算。e.g：1->2->3，即d[1]>d[2]>d[3]，如果1->2有两条路，那么这两条路都符合d[1]>d[2]的条件。虽然题目中描述Jimmy想从不同的路线经过，而事实上应该是不算重边的。

巴特西

UVA 10917 Walk Through the Forest（dijkstra+DAG上的dp）

最新文章

热门文章