【题目来源】
/problem/P2349
【题目描述】
有一盗墓者潜入一金字塔盗宝。当她(难道是 Lara Croft ?)打开一个宝箱的时候,突然冒出一阵烟(潘多拉的盒子?),她迅速意识到形势不妙,三十六计走为上计……由于她盗得了金字塔的地图,所以她希望能找出最佳逃跑路线。地图上标有 N 个室,她现在就在 1 室,金字塔的出口在 N 室。她知道一个秘密:那阵烟会让她在直接连接某两个室之间的通道内的行走速度减半。她希望找出一条逃跑路线,使得在最坏的情况下所用的时间最少。
【输入格式】
输入文件的第一行有两个正整数 N(3≤N≤100)和 M(3≤M≤2000);
N表示金字塔的出口所在的N室;
M表示有M 行数据,每行有三个数正整数 U 、V 、W,表示直接从 U 室跑到 V 室(V 室跑到 U 室)需要 W(3≤W≤255)秒。
【输出格式】
输出所求的最少时间(单位为秒)。
【输入样例】
7 8
1 2 10
2 3 12
3 4 20
4 7 8
1 7 34
2 5 10
5 6 12
6 4 13
【输出样例】
66
【说明/提示】
样例解释 Sample Explan:
基本上有三种路线:
(1)1→2→3→4→7。
总时间为:10+12+20+8=50,最坏的情况是“ 3→4 ”那一段,要多花 20 秒(因为行走速度减半),所以这条路选最坏需要 70 秒;
(2)1→2→5→6→4→7。
总时间为:10+10+12+13+8=53,最坏的情况是“ 6→4 ”那一段,要多花 13 秒,所以这条路选最坏需要 66 秒;
(3)1→7。
总时间为:34=34,最坏的情况是“ 1→7 ”那一段,要多花 34 秒,所以这条路选最坏需要 68 秒。
【算法代码】
/* 链式前向星存图val[idx] 表示第 idx 条边的权值。e[idx] 表示第 idx 条边的终点。ne[idx] 表示与第 idx 条边同起点的最近一次被添加的边的编号。h[a] 表示以结点 a 为起点的最近一次被添加的边的编号。这个表述是在使用ne[idx]=h[a] 时,也即使用h[a]=idx++ 更新 h[a] 之前而言的。要特别注意这个语境。*/#include<bits/stdc++.h>using namespace std;int n,m;const int maxn=105;const int maxm=;// Undirected edges are special directed edges, open doubleint e[maxm<<1],ne[maxm<<1],h[maxn],val[maxm<<1],idx;void add(int a,int b,int w) {val[idx]=w,e[idx]=b,ne[idx]=h[a],h[a]=idx++;}int ans=0x3f3f3f3f;void dfs(int from,int cur,int maxv,int sum) { //maxv:max value of current pathif(sum+maxv>ans) return;if(cur==n) {ans=min(sum+maxv,ans);return;}for(int j=h[cur]; j!=-1; j=ne[j]) {int t=e[j];if(t==from) continue;dfs(cur,t,max(maxv,val[j]),sum+val[j]);}}int main() {cin>>n>>m;memset(h,-1,sizeof(h));for(int i=1; i<=m; ++i) {int x,y,z;scanf("%d%d%d",&x,&y,&z);add(x,y,z);add(y,x,z);}dfs(0,1,0,0);cout<<ans<<endl;}/*in:7 81 2 102 3 123 4 204 7 81 7 342 5 105 6 126 4 13out:66*/
【参考文献】
/problem/solution/P2349
/qq_44343213/article/details/102957651
/m0_46304383/article/details/113457800