当前位置: 首页 > 工具软件 > Rescue! Max > 使用案例 >

zju 1053 FDNY to the Rescue!

左康安
2023-12-01

   做这道题的时候,自己恰好刚看过dijstra算法。不过感觉有些地方还是不是那么好处理?去网上看了一下,大家好像说这个题很简单,就感觉自己太菜了。下面写下自己做这个题的过程。
   首先,我要解决的是要存储消防站到火点的路径,并且是存储多个消防站到火点的路径,这个该怎么存储呢?此外,我要存储多个消防站到火点所用的时间,这个该怎么存储呢?还有,怎么根据输入消防站的个数不同来输出呢?这些都成为了我的困扰。
   后来看了网上的代码,感觉对我帮助很大。

    一、我用不用存储每个消防站到火点的路线呢?不用!!我只要将到达该点的最短路径的前驱存储就行了,用不着再用什么二维数组来存储消防站到火点的距离。举个例子,消防站标号为7,火点标号为2。我如何知道从消防站到火点的路径呢?就找7的前驱(假设为5),这个点就是消防站到火点的第一步,如果5的前驱不是2继续找5的前驱并继续下去,如果5的前驱是2了,那就结束。因此路径是7->5->2。
    二、消防站到火点的时间怎么存储呢?我设置一个数组d[],d[i]就代表从火点到i的最短时间。
    三、这个算法找到的是火点到各个路口的最短路径,但是我并不全要啊,我要的是那些消防站在的那些路口的数据。如何解决这个问题呢?我设置一个数组station[],对那些消防站在的那些路口进行标记。比如,1号路口有消防站,则将station[1]标记为1,二号路口没有消防站,则将station[2]标记为0。最后根据station[i]是否为1来进行输出。
    四、输出的时候要怎么处理呢?我如何保证对每个消防站都进行了输出呢?此时,我设置一个变量stasum记录消防站的个数,每输出一次,k++,当k!=stasum时,就保证输出结束了。
     这些仅仅是一些方面,有什么问题的欢迎交流。。我是菜鸟。。

 1 #include<iostream>  
 2 using namespace std;  
 3 #define MAXV 20  
 4 #define INF INT_MAX  
 5   
 6 int map[MAXV][MAXV],d[MAXV],parent[MAXV];  //d[i]表示是从火点到i点最短路径的长度 
 7 int n,fire,stasum,station[MAXV];  //parent[i]表示是在最短路径上i的前驱  fire表示的是火点所在的位置 
 8 //staion[i]的值用来标记消防站 
 9 void dijkstra(){  
10     int i,j,v,tmp;  
11     bool vis[MAXV];  
12     memset(parent,-1,sizeof(parent));  
13     memset(vis,false,sizeof(vis));  
14    for(i=1;i<=n;i++) d[i]=INF;  
15     d[fire]=0;  
16   
17     for(i=1;i<=n;i++){   
18         tmp=INF;  
19         for(j=1;j<=n;j++)  //这个过程是找出离火点最近的并且是没有访问过的路口 
20             if(d[j]<tmp && !vis[j]){  
21                 tmp=d[j];  
22                 v=j;  
23             }  
24         vis[v]=true;  
25         for(j=1;j<=n;j++){  
26             if(!vis[j] && map[v][j]!=-1 && d[j]>d[v]+map[v][j]){     //-1不能走  
27                 d[j]=d[v]+map[v][j];  
28                parent[j]=v;        //记录路径  
29             }  
30         }  
31     }  
32 }  
33  
34 void output(){  
35     int j,i,tmp,v;  
36     printf("Org Dest    Time    Path\n");  
37       
38     j=0;  
39     while(j!=stasum){  
40         tmp=INF;  
41         for(i=1;i<=n;i++){                   //每次找最小的时间输出  
42             if(station[i] && d[i]<tmp){  //注意我是要找消防站点输出的啊,必须要求station[i]==1 
43                tmp=d[i];  
44                 v=i;  
45             }  
46         }  
47         station[v]=0;                       //将这个站点设为非消防站点(这点也很重要啊) 
48         printf("%d  %d  %d",v,fire,d[v]);  
49         while(v!=-1){  
50             printf("    %d",v);  
51             v=parent[v];  
52         }  
53         cout<<endl;
54         j++;  
55     }  
56 }  
57   
58 int main(){  
59     int i,j,x;  
60     scanf("%d",&n);  
61     for(i=1;i<=n;i++){  
62         for(j=1;j<=n;j++){  
63             scanf("%d",&map[j][i]);     //边反向存储  
64         }  
65     }  
66     scanf("%d",&fire);  
67     stasum=0;  
68     memset(station,0,sizeof(station)); 
69     while(getchar()!='\n')
70   {
71     cin>>x;
72     station[x]=1; //标记消防站 
73     stasum++;  //计算消防站总数 
74   }
75     dijkstra();  
76     output();  
77     return 0;  
78 }

 

转载于:https://www.cnblogs.com/wangaohui/archive/2012/11/17/2774910.html

 类似资料:

相关阅读

相关文章

相关问答