洛谷 P2349：金字塔 ← 链式前向星 dfs
【题目来源】
https://www.luogu.com.cn/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 秒。
【算法代码】
/* 链式前向星存图
e[i] 表示第 i 条边的终点
ne[i] 表示与第 i 条边同起点的前一条边的编号（按边的添加顺序）
h[i] 表示以 i 为起点的当前边的编号（按边的添加顺序）
*/
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int maxn=105;
const int maxm=2005;
// Undirected edges are special directed edges, open double
int 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 path
if(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 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
out:
66
*/
【参考文献】
https://www.luogu.com.cn/problem/solution/P2349
https://blog.csdn.net/qq_44343213/article/details/102957651
https://blog.csdn.net/m0_46304383/article/details/113457800