飞行路线（分层图+dijstra+堆优化）（加上题目选数复习）

飞行路线

这一题除了堆优化和dijstra算法和链式前向星除外还多考了一个考点就是，分层图，啥叫分层图呢？简而言之就是一个三维的图，按照其题意来说有几个可以免费的点就有几层，而且这个分层的权值为0（这样就相当于免费了）， 怎么来理解这个意思呢？就是相当于这个dijstra算法它遍历的不再是一个一维图而是一个三维图，本质还是一样的，由于我们储存的边信息用的是链式前向星，所有所有的边都是按照顺序结构存放在一个一个顺序表中，所以我们不用担心空间复杂度的问题，只需要担心时间复杂度，但是由于我们用到了对堆优化。这一题就是相当于将前面的堆优化就上dijstra算法加上链式前向星重新复习一遍。

代码如下

#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
const int M = 2e5;
const int N = 5e6;
int ans[N], cnt = 0, head[N], s, t, n, m, k;
bool vis[N];
//优先队列的结构体
struct node {int id;int dis;bool operator< (const node& x) const {return x.dis < dis;}
};
//优先队列
priority_queue<node> q;
//边的结构体
struct EDGE
{int next;int w;int to;
}e[N];
//键边函数
void add(int u, int v, int w)
{e[++cnt].w = w;e[cnt].to = v;e[cnt].next = head[u];head[u] = cnt;
}
//dijstra函数
void dijstra()
{ans[s] = 0;q.push(node{ s,0 });while (!q.empty()){node tmp = q.top();q.pop();int k = tmp.id;if (vis[k])continue;vis[k] = true;for (int i = head[k]; i != 0; i = e[i].next){int to = e[i].to;if (!vis[to] && ans[to] > ans[k] + e[i].w){ans[to] = ans[k] + e[i].w;q.push(node{ to,ans[to] });}}}
}int main()
{cin >> n >> m >> k;cin >> s >> t;s++;t++;memset(ans, 0x3f, sizeof(ans));for (int i = 1; i <= m; i++){int u, v, w;cin >> u >> v >> w;++u;++v;add(u, v, w);add(v, u, w);for (int j = 1; j <= k; j++) {add(u + (j - 1) * n, v + j * n, 0);add(v + (j - 1) * n, u + j * n, 0);add(v + j * n, u + j * n, w);add(u + j * n, v + j * n, w);}}dijstra();int anss = 0x7fffffff;for (int i = 0; i <= k; i++){if (anss > ans[t + i * n]){anss = ans[t + i * n];}}cout << anss << endl;return 0;
}

选数

为什么要重新写一下这一题，因为我在这题错过两遍了，为了防止错三遍 ，再写一遍，结果终于是在没有外力靠住下写出来了
主要思路还是深搜：在dfs函数中需要定义三个变量，第一是就是一记录有多少个答案，第二就是就是for循环的下标，第三就是sum用于记录这个和。

代码如下（我竟然真的靠自己完全写出来的）

#include<iostream>
#include<queue>
#include<algorithm>
#include<cmath>
using namespace std;
int n,m;
int a[100000];
bool ispear(int x)
{if(x==1)return false;if(x==2)return true;if(x>3){for(int i=2;i<=sqrt(x);i++){if(x%i==0)return false;}}return true;
}
int ans=0;
void dfs(int sum,int step,int cnt)
{if(cnt>=m){if(ispear(sum)){ans++;}return ;}for(int i=step+1;i<=n;i++){dfs(sum+a[i],i,cnt+1);}
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];dfs(0,0,0);cout<<ans<<endl;return 0;
}