网站需要审核吗,设计有哪些网站,天津网站建设哪里好,网站后台支持的字体常见情形#xff1a; 对于边有k次操作的题。。 整体思想#xff1a; 分层图最短路可以视作是dijkstra的一个扩展#xff0c;通常用于处理N小于10000#xff0c;或者是k不大的情形。整体有点类似于拆点。将一个点拆成k个点处理。层与层之间互不影响。 好了我就说这么多… 常见情形 对于边有k次操作的题。。 整体思想 分层图最短路可以视作是dijkstra的一个扩展通常用于处理N小于10000或者是k不大的情形。整体有点类似于拆点。将一个点拆成k个点处理。层与层之间互不影响。 好了我就说这么多剩下来的交给想象力这个自己相通了就不难理解。 经典例题 一3095. 冻结 “我要成为魔法少女” “那么以灵魂为代价你希望得到什么” “我要将有关魔法和奇迹的一切封印于卡片之中......” 在这个愿望被实现以后的世界里人们享受着魔法卡片SpellCard又名符卡带来的便捷。 现在不需要立下契约也可以使用魔法了 你还不来试一试 比如我们在魔法百科全书Encyclopedia of Spells里用“freeze”作为关键字来查询会有很多有趣的结果。 例如我们熟知的 Cirno她的冰冻魔法当然会有对应的 SpellCard 了。 当然更加令人惊讶的是居然有冻结时间的魔法Cirno 的冻青蛙比起这些来真是小巫见大巫了。 这说明之前的世界中有很多魔法少女曾许下控制时间的愿望比如 Akemi Homura、Sakuya Izayoi...... 当然在本题中我们并不是要来研究历史的而是研究魔法的应用。 我们考虑最简单的旅行问题吧 现在这个大陆上有 NN 个城市MM 条双向的道路。 城市编号为 1∼N1∼N我们在 11 号城市需要到 NN 号城市怎样才能最快地到达呢 这不就是最短路问题吗 我们都知道可以用 Dijkstra、Bellman-Ford、Floyd-Warshall 等算法来解决。 现在我们一共有 KK 张可以使时间变慢 50%50% 的 SpellCard也就是说在通过某条路径时我们可以选择使用一张卡片这样我们通过这一条道路的时间就可以减少到原先的一半。 需要注意的是 在一条道路上最多只能使用一张 SpellCard。使用一张 SpellCard 只在一条道路上起作用。你不必使用完所有的 SpellCard。 给定以上的信息你的任务是 求出在可以使用这不超过 KK 张时间减速的 SpellCard 之情形下从城市 11 到城市 NN 最少需要多长时间。 输入格式 第一行包含三个整数N、M、KN、M、K。 接下来 MM 行每行包含三个整数Ai、Bi、TimeiAi、Bi、Timei表示存在一条 AiAi 与 BiBi 之间的双向道路在不使用 SpellCard 之前提下通过它需要 TimeiTimei 的时间。 输出格式 输出一个整数表示从 11 号城市到 NN 号城市的最小用时。 数据范围 1≤K≤N≤501≤K≤N≤50, 1≤M≤10001≤M≤1000, 1≤Ai,Bi≤N1≤Ai,Bi≤N, 2≤Timei≤20002≤Timei≤2000, 为保证答案为整数保证所有的 TimeiTimei 均为偶数。 所有数据中的无向图保证无自环、重边且是连通的。 输入样例 4 4 1
1 2 4
4 2 6
1 3 8
3 4 8输出样例 7样例解释 在不使用 SpellCard 时最短路为 1→2→41→2→4总时间为 1010。 现在我们可以使用 11 次 SpellCard那么我们将通过 2→42→4 这条道路的时间减半此时总时间为 77。 #includebits/stdc.h
using namespace std;
const int N60,M2010;
typedef pairint,pairint,intPII;
int h[N],e[M],ne[M],w[M],idx;
int dis[N][N];
bool st[N][N];
int n,m,k;
void add(int a,int b,int c){e[idx]b,w[idx]c,ne[idx]h[a],h[a]idx;
}
void dij()
{memset(dis,0x3f,sizeof dis);priority_queuePII,vectorPII,greaterPIIq;q.push({0,{1,0}});dis[1][0]0;while(q.size()){auto tq.top();q.pop();int vt.second.first;int ut.second.second;if(st[v][u]){continue;}st[v][u]true;for(int ih[v];~i;ine[i]){int je[i];if(st[j][u]){continue;}if(u1k){if(dis[j][u1]dis[v][u]w[i]/2){dis[j][u1]dis[v][u]w[i]/2;q.push({dis[j][u1],{j,u1}});}}if(dis[j][u]dis[v][u]w[i]){dis[j][u]dis[v][u]w[i];q.push({dis[j][u],{j,u}});}}}
}
void solve()
{cinnmk;memset(h,-1,sizeof h);for(int i1;im;i){int a,b,c;cinabc;add(a,b,c);add(b,a,c);}dij();int ans0x3f3f3f3f;for(int i0;ik;i){//coutdis[n][i]endl;ansmin(dis[n][i],ans);}coutans;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);solve();return 0;
}二340. 通信线路 在郊区有 NN 座通信基站PP 条 双向 电缆第 ii 条电缆连接基站 AiAi 和 BiBi。 特别地11 号基站是通信公司的总站NN 号基站位于一座农场中。 现在农场主希望对通信线路进行升级其中升级第 ii 条电缆需要花费 LiLi。 电话公司正在举行优惠活动。 农产主可以指定一条从 11 号基站到 NN 号基站的路径并指定路径上不超过 KK 条电缆由电话公司免费提供升级服务。 农场主只需要支付在该路径上剩余的电缆中升级价格最贵的那条电缆的花费即可。 求至少用多少钱可以完成升级。 输入格式 第 11 行三个整数 NPKNPK。 第 2..P12..P1 行第 i1i1 行包含三个整数 Ai,Bi,LiAi,Bi,Li。 输出格式 包含一个整数表示最少花费。 若 11 号基站与 NN 号基站之间不存在路径则输出 −1−1。 数据范围 0≤KN≤10000≤KN≤1000, 1≤P≤100001≤P≤10000, 1≤Li≤10000001≤Li≤1000000 输入样例 5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6输出样例 4#includebits/stdc.h
using namespace std;
typedef pairint, pairint, intPII;
const int N 1010,M20010;
int h[N], e[M], ne[M], w[M], idx;
int dis[N][N];
bool st[N][N];
int n, m, k;
int ans0x3f3f3f3f;
void add(int a, int b, int c) {e[idx] b, w[idx] c, ne[idx] h[a], h[a] idx;
}
void dij()
{memset(dis, 0x3f, sizeof dis);priority_queuePII, vectorPII, greaterPIIq;q.push({ 0,{1,0} });dis[1][0] 0;while (q.size()) {auto t q.top();q.pop();int v t.second.first;int u t.second.second;if (st[v][u]) {continue;}st[v][u] true;for (int i h[v];~i;i ne[i]) {int j e[i];if (st[j][u]) {continue;}if (u 1 k) {if (dis[j][u 1] dis[v][u] ) {dis[j][u 1] dis[v][u] ;q.push({ dis[j][u 1],{j,u 1} });}}if (dis[j][u] max(dis[v][u] , w[i])) {dis[j][u] max( dis[v][u] , w[i]);q.push({ dis[j][u], { j,u } });}}}
}
void solve()
{cin n m k;memset(h, -1, sizeof h);for (int i 1;i m;i) {int a, b, c;cin a b c;add(a, b, c);add(b, a, c);}dij();for (int i 0;i k;i) {//cout dis[n][i] endl;ans min(ans, dis[n][i]);}if (ans 0x3f3f3f3f) {cout -1;}else {cout ans;}
}
int main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);solve();return 0;
}
