【最短路问题】
第一道 最短路问题+DFS 各种WA RE 还是在参照大神的代码的情况下
http://acm.hdu.edu.cn/showproblem.php?pid=1142
只是照搬 自己熟悉下过程 dijkstra+dfs
#include <cstdio>
#include <cstring>
#define INF 2000000000
#define N 1010
using namespace std;
int map[N][N],lowcost[N],visited[N],d[N],p[N];
void dijkstra(int s,int n)
{
int i,j,k,min;
memset(visited,0,sizeof(visited));
for(i=1;i<=n;i++)
{
lowcost[i]=map[s][i];
}
d[s]=0;visited[s]=1;
for(i=1;i<n;i++)
{
min=INF;k=i;
for(j=1;j<=n;j++)
{
if(!visited[j]&&min>lowcost[j])
{
min=lowcost[j];
k=j;
}
}
d[k]=min;visited[k]=1;
for(j=1;j<=n;j++)
{
if(!visited[j]&&lowcost[j]>d[k]+map[k][j]) //visited[j] 错误写成visited
{ // d[k]+map[k][j] 会 ACCESS_VIOLATION
lowcost[j]=d[k]+map[k][j];
}
}
}
}
int DFS(int s,int n)
{
if(p[s]) return p[s];
if(s==2) return 1;
int i,sum;
sum=0;
for(i=1;i<=n;i++)
{
if(map[s][i]<INF&&d[s]>d[i])
{
if(p[i]) sum+=p[i];
else sum+=DFS(i,n);
}
}
sum=sum+p[s];
p[s]=sum;
return p[s];
}
int main()
{
int i,j,n,m,t1,t2,w;
while(scanf("%d",&n),n)
{
scanf("%d",&m);
memset(p,0,sizeof(p));
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
map[i][j]=(i==j?0:INF);
}
}
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&t1,&t2,&w);
map[t1][t2]=map[t2][t1]=w;
}
dijkstra(2,n);
printf("%d\n",DFS(1,n));
}
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/187133.html原文链接：https://javaforall.net
