http://acm.hdu.edu.cn/showproblem.php?pid=1142迪杰斯特拉算法+DFS
#include <iostream>
using namespace std;
const int MAX=1000001;
int pi[1001],path[1001][1001],n,dp[1001];
bool visit[1001];
void SP(int v) //有向图最短路径,迪杰斯特拉算法
{
int i,min,j,temp;
for(i=1;i<=n;i++)
{
visit[i]=false;
pi[i]=path[i][v];
}
visit[v]=true;
pi[v]=0;
for(i=1;i<n;i++)
{
min=MAX;
for(j=1;j<=n;j++)
if(!visit[j] && pi[j]<min)
{
temp=j;
min=pi[j];
}
if(min==MAX)
break;
visit[temp]=true;
for(j=1;j<=n;j++)
if(!visit[j] && pi[j]>min+path[temp][j])
pi[j]=min+path[temp][j];
}
}
int dfs(int v) //记忆化深搜
{
if(dp[v]!=-1)
return dp[v];
if(v==2)
return 1;
int i;
dp[v]=0;
for(i=1;i<=n;i++)
if(path[i][v]!=MAX && pi[i]<pi[v])
dp[v]+=dfs(i);
return dp[v];
}
int main()
{
int m,i,j,k,p;
while(scanf("%d",&n),n)
{
scanf("%d",&m);
for(i=1;i<=n;i++)
{
dp[i]=-1;
for(j=1;j<=n;j++)
path[i][j]=MAX;
}
for(k=0;k<m;k++)
{
scanf("%d%d%d",&i,&j,&p);
path[i][j]=path[j][i]=p;
}
SP(2);
cout<<dfs(1)<<endl;
}
}posted on 2011-04-26 12:10
大大木马 阅读(354)
评论(0) 编辑 收藏 引用