今天写完这道题，感觉自己理论实践衔接的还是不够呀，思想会，代码不会打；从易到难，慢慢开始吧～
其实代码参考(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
- 头文件：#include <string.h>
- 一般用于填充char数组
- 用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一样
其他就自己看官方文档吧，语言相关的东西只有一直用才能记住，否则就会忘的很快，但既然学过，重新捡起来肯定比从无到有快！
