深圳网站seo,三亚人才招聘网站,谷搜易外贸网站建设,上海建设工程交易网题目描述 “我要成为魔法少女#xff01;” “那么#xff0c;以灵魂为代价#xff0c;你希望得到什么#xff1f;” “我要将有关魔法和奇迹的一切#xff0c;封印于卡片之中„„” 在这个愿望被实现以后的世界里#xff0c;人们享受着魔法卡片#xff08;\(SpellCard\…题目描述 “我要成为魔法少女” “那么以灵魂为代价你希望得到什么” “我要将有关魔法和奇迹的一切封印于卡片之中„„” 在这个愿望被实现以后的世界里人们享受着魔法卡片\(SpellCard\)又名符卡带来的便捷。 现在不需要立下契约也可以使用魔法了你还不来试一试 比如我们在魔法百科全书\(Encyclopedia of Spells\)里用“\(freeze\)”作为关键字来查询会有很多有趣的结果。 例如我们熟知的\(Cirno\)她的冰冻魔法当然会有对应的 \(SpellCard\) 了。 当然更加令人惊讶的是居然有冻结时间的魔法\(Cirno\) 的冻青蛙比起这些来真是小巫见大巫了。 这说明之前的世界中有很多魔法少女曾许下控制时间的愿望比如 \(Akemi Homura\)、\(Sakuya Izayoi\)、„„ 当然在本题中我们并不是要来研究历史的而是研究魔法的应用。 我们考虑最简单的旅行问题吧 现在这个大陆上有 \(N\) 个城市\(M\) 条双向的道路。城市编号为 \(1~N\)我们在 \(1\) 号城市需要到 \(N\) 号城市怎样才能最快地到达呢 这不就是最短路问题吗我们都知道可以用 \(Dijkstra、Bellman-Ford、Floyd-Warshall\)等算法来解决。 现在我们一共有 K 张可以使时间变慢 \(50\%\)的 \(SpellCard\)也就是说在通过某条路径时我们可以选择使用一张卡片这样我们通过这一条道路的时间 就可以减少到原先的一半。需要注意的是 在一条道路上最多只能使用一张 \(SpellCard\)。使用一张\(SpellCard\) 只在一条道路上起作用。你不必使用完所有的 \(SpellCard\)。 给定以上的信息你的任务是求出在可以使用这不超过 \(K\) 张时间减速的 \(SpellCard\) 之情形下从城市\(1\) 到城市\(N\)最少需要多长时间。输入输出格式 输入格式 第一行包含三个整数\(N、M、K\)。 接下来 \(M\) 行每行包含三个整数\(A_i、B_i、Time_i\)表示存在一条 \(A_i\)与 \(B_i\)之间的双向道路在不使用 \(SpellCard\) 之前提下通过它需要 \(Time_i\)的时间。 输出格式 输出一个整数表示从\(1\) 号城市到 \(N\)号城市的最小用时。 输入输出样例 输入样例#1 4 4 1
1 2 4
4 2 6
1 3 8
3 4 8 输出样例#1 7 说明 样例解释 在不使用 \(SpellCard\) 时最短路为 \(1à2à4\)总时间为 \(10\)。现在我们可以使用 \(1\) 次 \(SpellCard\)那么我们将通过 \(2à4\) 这条道路的时间减半此时总时间为\(7\)。 对于\(100\%\)的数据\(1 ≤ K ≤ N ≤ 50M ≤ 1000\)。\(1≤ A_iB_i ≤ N2 ≤ Time_i ≤ 2000\)。 为保证答案为整数保证所有的 \(Time_i\)均为偶数。 所有数据中的无向图保证无自环、重边且是连通的。 思路还是跟其他的分层最短路题目一样只不过之前的\(k\)次免费的机会变成了\(k\)次免费缩小到一半的机会那么分层的时候我们把边权由\(0\)改为\(w/2\)就可以了。 代码 #includecstdio
#includecstring
#includequeue
#includealgorithm
#includecctype
#define maxn 5000001
using namespace std;
int n,m,k,head[maxn],num,dis[maxn],s,t;
inline int qread() {char cgetchar();int num0,f1;for(;!isdigit(c);cgetchar()) if(c-) f-1;for(;isdigit(c);cgetchar()) numnum*10c-0;return num*f;
}
struct Edge {int v,w,nxt;
}e[maxn];
struct node {int x,y;bool operator (const node a) const {return ya.y;}
};
inline void ct(int u, int v, int w) {e[num].vv;e[num].ww;e[num].nxthead[u];head[u]num;
}
priority_queuenodeq;
inline void dijkstra() {memset(dis,0x3f,sizeof(dis));dis[1n*k]0;q.push((node){1n*k,0});while(!q.empty()) {int uq.top().x,dq.top().y;q.pop();if(d!dis[u]) continue;for(int ihead[u];i;ie[i].nxt) {int ve[i].v;if(dis[v]dis[u]e[i].w) {dis[v]dis[u]e[i].w;q.push((node){v,dis[v]});} }}
}
int main() {nqread(),mqread(),kqread();for(int i1,u,v,w;im;i) {uqread(),vqread(),wqread();for(int j0;jk;j) {ct(uj*n,vj*n,w);ct(vj*n,uj*n,w);if(j) {ct(uj*n,v(j-1)*n,w/2);ct(vj*n,u(j-1)*n,w/2);} }}dijkstra();int zrj0x7fffffff;for(int i0;ik;i) zrjmin(zrj,dis[ni*n]);printf(%d\n,zrj);return 0;
} 转载于:https://www.cnblogs.com/grcyh/p/10134341.html
