360搜索建站,设计网页,icp备案号怎么填写,公司运营策划方案飞行路线 这一题除了堆优化和dijstra算法和链式前向星除外还多考了一个考点就是#xff0c;分层图#xff0c;啥叫分层图呢#xff1f;简而言之就是一个三维的图#xff0c;按照其题意来说有几个可以免费的点就有几层#xff0c;而且这个分层的权值为0#xff08;这样就相…飞行路线 这一题除了堆优化和dijstra算法和链式前向星除外还多考了一个考点就是分层图啥叫分层图呢简而言之就是一个三维的图按照其题意来说有几个可以免费的点就有几层而且这个分层的权值为0这样就相当于免费了 怎么来理解这个意思呢就是相当于这个dijstra算法它遍历的不再是一个一维图而是一个三维图本质还是一样的由于我们储存的边信息用的是链式前向星所有所有的边都是按照顺序结构存放在一个一个顺序表中所以我们不用担心空间复杂度的问题只需要担心时间复杂度但是由于我们用到了对堆优化。这一题就是相当于将前面的堆优化就上dijstra算法加上链式前向星重新复习一遍。
代码如下
#includeiostream
#includequeue
#includestring.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_queuenode 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用于记录这个和。
代码如下我竟然真的靠自己完全写出来的
#includeiostream
#includequeue
#includealgorithm
#includecmath
using namespace std;
int n,m;
int a[100000];
bool ispear(int x)
{if(x1)return false;if(x2)return true;if(x3){for(int i2;isqrt(x);i){if(x%i0)return false;}}return true;
}
int ans0;
void dfs(int sum,int step,int cnt)
{if(cntm){if(ispear(sum)){ans;}return ;}for(int istep1;in;i){dfs(suma[i],i,cnt1);}
}
int main()
{cinnm;for(int i1;in;i)cina[i];dfs(0,0,0);coutansendl;return 0;
}
