<图算法 pta> 1003 Emergency (25 分)

  今天写完这道题,感觉自己理论实践衔接的还是不够呀,思想会,代码不会打;从易到难,慢慢开始吧~

  其实代码参考(chao)了《算法笔记》

  这是一道对dijkstra算法进行应用的题目;其中新增了点权,边权应该是老朋友,但问题是题目要求最短路径数量与最大点权。如何在算法运行时维护这两个值是我之前没涉及过的。所以果断以例题的方式学习这道题,看了书里的解析。

 

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int inf=1000000; 
int main(void){
    int visited[501]={0};//城市访问数组 
    int rescue[501]={0};//救援队数量
    int dist[501]={0};//到各点最短距离 
    int edge[501][501]={0};
    int n,m,c1,c2;
    scanf("%d %d %d %d",&n,&m,&c1,&c2);
    for(int i=0;i<n;i++){
        scanf("%d",&rescue[i]);        
    }
    fill(edge[0],edge[0]+501*501,inf);//用于初始化
    fill(dist,dist+501,inf);
    dist[c1]=0;
     
    for(int i=0;i<m;i++){//构造图 
        int t1,t2,value;
        scanf("%d %d %d",&t1,&t2,&value);
        edge[t1][t2]=value;
        edge[t2][t1]=value;
    }

    int w[501]={0};
    int path_num[501]={0};
    w[c1]=rescue[c1];
    path_num[c1]=1;
    for(int i=0;i<n;i++){
        int minn=inf,minn_index=-1;
        for(int j=0;j<n;j++){
            if(minn>dist[j]&&visited[j]==0){
                minn=dist[j];    
                minn_index=j;
            }
        }
        if(minn_index==-1) break;
        visited[minn_index]=1;
        for(int j=0;j<n;j++){
            if(visited[j]==0&&edge[minn_index][j]!=inf){
                if(dist[j]>dist[minn_index]+edge[minn_index][j]){//若当前路径比绕一圈满,则修改 
                    dist[j]=dist[minn_index]+edge[minn_index][j];
                    w[j]=w[minn_index]+rescue[j];
                    path_num[j]=path_num[minn_index]; //覆盖path_num[j] 
                }
                else if(dist[j]==dist[minn_index]+edge[minn_index][j]){
                    path_num[j]=path_num[minn_index]+path_num[j];//最短路径条数与点权无关,写外面 
                    if(w[j]<w[minn_index]+rescue[j]){ //若当前救援队数量更多 
                        w[j]=w[minn_index]+rescue[j];//继承更多救援队的 
                    }
                }
            }
        }
    }
    

    printf("%d %d\n",path_num[c2],w[c2]);
    return 0;
}

 

因为很久没接触c++的STL了,以前很多好用的数据结构都忘了,所以也想不到

  总结一下今天学习的东西

Q1:memset与fill的区别

  memset

  1. 头文件:#include <string.h>
  2. 一般用于填充char数组
  3. 用memset填充int数组的话,只能赋值0,-1,INF(0x3f3f3f3f),否则会出错,直接赋值为-1

    fill

  头文件:#include <algorithm>

    可以任意赋值 fill(起始位置,末尾,值) 

   fill(edge[0],edge[0]+501*501,inf);  给一个二维数组赋值

 

Q2:我不记得vector怎么用了...于是我去阅读了文档

  总结一下vector特性:

    1.vector是一个可以改变大小的数组,访问数组中某元素二者效率一致。 但vector的大小改变由容器自动处理

    2.当新元素插入时,vector可能需申请新的数组并把所有元素移动过去,但vector不是每次插入都这样做。

    3.承接上述问题,vector其实留一手,虽说动态增长,但他还是会多申请一点空间,以应对不时之需

    4.官方建议插入需要在指数级增长的间隔进行,这样才能平摊时间复杂度?(不太懂

      但在网上看到别人的博客,是对vector插入与list插入做了对比;前者性能更好,原因应该是vector留一手特性使然,使得在尾部插入效率很高,而list每次插入需要新申请一个节点,故vector插入效率上还是很强的

      但官方文档上说如果在某个特定位置插入、删除,则vector比deque,list和forward_list差

    5.与数组比较起来,vector因为其有效管理存储和动态增长的特性更消耗内存

  新建一个vector: vector<int> num[size]. <>里面也可以是结构体,可以用作图的领接存储

  在尾部插入新元素:push_back()

  empyt() 检查vector是否为空

  capacity() 返回vector实际分配的大小

  shrink_to_fit() c++11才支持 就是让capacity和size一样 

  其他就自己看官方文档吧,语言相关的东西只有一直用才能记住,否则就会忘的很快,但既然学过,重新捡起来肯定比从无到有快!

 <图算法 pta> 1003 Emergency (25 分)

<图算法 pta> 1003 Emergency (25 分)

 

上一篇:2022-2023学年英语周报七年级第25期答案及试题


下一篇:列车调度 (25 分)(STL)