hdu 1142_hdu1001

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

【最短路问题】

第一道 最短路问题+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;
}