12.19 单源最短路（dij，dp），最快逃跑方式（贪心模拟）

P1359 租用游艇

就是说第一行为1到2~n,第二行为2到3~N.最终构建出来的是一个无向图，

然后源点是1，目标点是n,问从1到n的最短路

dp

#include<iostream>
#include<queue>
using namespace std;
int dp[201];//表示从i号到n所需的最少成本
int n;
int arr[201][201];
int main() {
	cin >> n;
	for (int i = 1; i <= n - 1; i++) {//i表示起点
		for (int j = i + 1; j <= n; j++) {//j表示终点
			cin >> arr[i][j];
		}
		dp[i] = 1e9;
	}

	for (int i = n - 1; i >= 1; i--) {//i表示初始状态
		for (int j = i + 1; j <= n; j++) {//j表示终点
			dp[i] = min(dp[i], arr[i][j] + dp[j]);//表示划分子问题，要向到n位，就要到j位，要到J位，就要到i位，从i位到j位需要arr[i][j]的代价
		}//min的后项表示状态转移，从i转移到j
	}
	cout << dp[1];
	return 0;
}

从高处往低处更新，这样可以保证在低处调用高处的dp时，是唯一确定的，就是不会再被更新的大小

如果从低处往高处更新，就是类似于dij的思路，但又不完全是?

最短路

dij的想法就是每次迭代，找到一个未访问过的，距离最近的点，找到后，就依据这个点去更新dis数组。dis数组记录的是固定起点到不同终点的最短距离，其下标就代表着终点的编号。

也是划分的一个思想，就是找到一个新点后，看通过新点到目标点的代价小，还是原来的代价小

即dis[j]=min(dis[j],dis[u]+g[u][j])

dis[u]表示先到u点，g[u][j]表示通过u点再到j点

#include<iostream>
#include<queue>
using namespace std;
int g[201][201];
int n;
int dis[201];
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {//i表示起点
		for (int j = 1; j <= n; j++) {//j表示终点
			g[i][j] = 9999999;
			if (i == j)g[i][j] = 0;
		}
	}
	for (int i = 1; i <= n - 1; i++) {
		for (int j = i + 1; j <= n; j++) {
			cin >> g[i][j];
		}
	}
	for (int i = 2; i <= n; i++) {
		dis[i] = g[1][i];
	}
	dis[1] = 0;
	bool vis[201];
	memset(vis, 0, sizeof(vis));
	vis[1] = 1;
	for (int i = 1; i <= n - 1; i++) {//这个含义只表示迭代次数
		int mind = 99999999, u ;//注意已被访问的dis不可能再被更新，因为其是在可达的最小基础上直接到达的，而其他的方式，即使后续的代价很小，但因为第一步的代价就已经不如了，所以也不可能再被更新，就是类似于三角形任意两边和大于第三边，即使两边中有一边很短
		//但需注意，可以确定的是最小的未访问的dis元素，而不是任意的未访问的dis元素，每次的最小dis元素都不可能再被更新了
		for (int j = 2; j <= n;j++) {//每次都从此时dis数组里最小的点出发，这个循环的目的是为了找到此时dis数组里未被访问的最小的元素
			if (!vis[j]&&dis[j]<mind) {
				mind = dis[j];
				u = j;
			}
		}
		//由于每次都会访问掉一个点，所以每次可供选择的点越来越少,即每次迭代都会确定一个最终的点
		//不可能有更短的距离到这个点了，除非有负权，即一开始到u点的代价可能比较大，但是u到v有一个负权，使其可以完全弥补掉一开始很大的代价
		//如果没有负权，那么此时直接在可达的所有路径中找，第一次找到的所有路里最小的就是最后的结果，通过其他路再到同样的基于该最小路到的点，一定没有通过此时最小路到的代价小
		//因为没有负权，那么后续的所有路径都是建立在开始的一个很大的代价基础上，且没有负权可以减小这个代价
		vis[u] = 1;
		for (int j = 2; j <= n; j++) {
			dis[j] = min(dis[j], dis[u] + g[u][j]);//在此时已确定的新节点基础上向外延申
		}
	}
	cout << dis[n];
	return 0;
}

小优化?

dij得到的是单源点到各个点的最短距离，但如果只关心某一个点的最短距离，那么在迭代中得到u=n时就可以直接退出

	//dij算法得到的是源点到所有点的最短路径
	for (int i = 1; i <= n - 1; i++) {//每次确定一个dis,那么共需要迭代N-1轮
		int mind = 1e9, u;
		for (int j = 2; j <= n; j++) {//由于是到所有点的最短路径，所以除了自身以外，其他所有点都要不断去尝试更新
			//如果说是特指n的话，那么在这里取出的是n时，就意味着后续都不可能再更新出更低的成本了
			if (!vis[j] && dis[j] < mind) {
				mind = dis[j];
				u = j;
			}
		}
		vis[u] = 1;
		if (u == n)break;
		for (int j = 2; j <= n; j++) {
			dis[j] = min(dis[j], dis[u] + g[u][j]);//原策略，或者先到U,再通过u到j
			//注意这一步是依据新点u来更新各个dis元素
		}
	}

BOOL类型要初始化

在C++中，bool类型的数组未初始化时，其元素的值是不确定的，可能是true，也可能是false。因此，使用未初始化的bool数组时需要谨慎，最好先对其进行初始化操作，以确保其元素的值是可预测的。

少了memset就会报错

memset就是初始化，用for也行

它的头文件是string.h

P1095 [NOIP2007 普及组] 守望者的逃离

贪心的话，优先就是用魔法，直到距离很短

DP

dp[t][m]表示剩余时间为t,魔力剩余为m时所能走的最远距离

dp[t][m]=max(dp[t-1][m+4],dp[t-1][m]+17,dp[t-1][m-10]+60);

//这么一看有点像BFS

贪心，模拟（模拟为主）

int m, s, t;
	cin >> m >> s >> t;
	int s1 = 0, s2 = 0;
	//s1就是优先跑步，s1存为最优策略
	for (int i = 1; i <= t; i++) {
		s1 += 17;
		if (m >= 10) {
			s2 += 60;
			m -= 10;
		}//s2只能一直闪现，因为闪现的总体收益是更高的
		else {
			m += 4;
		}
		if (s2 > s1) {//如果闪现在某个时刻更好，就让s1保持，表示这之前都不跑而是来闪现
			s1 = s2;
		}
		if (s1 >= s) {
			cout << "Yes" << endl;
			cout << i << endl;
			return 0;
		}
	}
	cout << "No" << endl;
	cout << s1;