UVA 10917 Walk Through the Forest(dijkstra+DAG上的dp)

时间:2021-01-29 15:57:04

用新模板阿姨了一天,换成原来的一遍就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想从不同的路线经过,而事实上应该是不算重边的。