PAT学到了 2019/9/7

【4号做了一下PAT的代码仓库，我像一个傻子开着vs提交git，结果一直提示commit failed，用shell一个个文件add才发现是自己现在正在写的题的文件被锁住了=/=，PAT教给了我很多，比如一定不能变成一个弱智。 】

1.Dijkstra

void Dijkstra() {
	while (!visited[D]) {
		int v = -1, min = INF;
		for (int i = 0; i < N; i++) {
			if (!visited[i] && dis[i] < min) {
				v = i;
				min = dis[i];
			}
		}
		if (v == -1) return;//未联通
		visited[v] = true;//访问该点
		for ( edge&e : graph[v] ) {
			if (!visited[e.v] && dis[e.v] > dis[v] + e.dis ){
				dis[e.v] = dis[v] + e.dis;
				cost[e.v] = cost[v] + e.cost;
				pathLast[e.v] = v;
			}
			else if(dis[e.v] == dis[v]+ e.dis && cost[e.v]> cost[v] + e.cost){//花费更少
				cost[e.v] = cost[v] + e.cost;
				pathLast[e.v] = v;
			}
		}
	}
}

2.Dijkstra所需数据结构

struct edge {
	int v,dis,cost;//末端结点、距离、权重
	edge( int _v, int _d, int _c) {
		v = _v;
		dis = _d;
		cost = _c;
	}
};
vector<vector<edge> > graph(505);
int dis[505], cost[505], pathLast[505];//起点到该点的距离,起点到该点的最小权重,起点到该点的父节点
bool visited[505] = {false};

3.Dijkstra初始化

	for (int i = 0; i < M; i++) {
		scanf("%d %d %d %d", &a, &b, &c, &d);
		graph[a].push_back(edge(b, c, d));
		graph[b].push_back(edge(a, c, d));
	}
	fill(dis, dis + N, INF);
	fill(cost, cost + N, INF);
	dis[S] = cost[S] = 0;
	Dijkstra();

4.回文串的常用函数

string.substr(pos,n);

reverse(string.begin(),string.end());

5 .大数运算的结果对1000000007取模 防止溢出

6. getchar()吃掉getline()前面的回车

7.几个基础排序：

直接插入排序的算法思路：

（1） 设置监视哨r[0]，将待插入记录的值赋值给r[0]；

（2） 设置开始查找的位置j；

（3） 在数组中进行搜索，搜索中将第j个记录后移，直至r[0].key≥r[j].key为止；

（4） 将r[0]插入r[j+1]的位置上。

快速排序算法通过多次比较和交换来实现排序，其排序流程如下： 

(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。 

(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。

(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

bool isprime(int a) {
	if (a == 1) return false;
	for (int i = 2; i <= sqrt(a); i++) {
		if (a % i == 0) return false;
	}
	return true;
}