金字塔

题目描述

有一盗墓者潜入一金字塔盗宝。当她（难道是 Lara Croft ?）打开一个宝箱的时候，突然冒出一阵烟（潘多拉的盒子？），她迅速意识到形势不妙，三十六计走为上计……由于她盗得了金字塔的地图，所以她希望能找出最佳逃跑路线。地图上标有 $N$ 个室，她现在就在 $1$ 室，金字塔的出口在 $N$ 室。她知道一个秘密：那阵烟会让她在直接连接某两个室之间的通道内的行走速度减半。她希望找出一条逃跑路线，使得在最坏的情况下所用的时间最少。

输入格式

输入文件的第一行有两个正整数 $N$（$3 \le N \le 100$）和 $M$（$3 \le M \le 2000$）；下面有 $M$ 行，每行有三个数正整数 $U$ 、 $V$ 、 $W$，表示直接从 $U$ 室跑到 $V$ 室（$V$ 室跑到 $U$ 室）需要 $W$（$3 \le W \le 255$）秒。

输出格式

输出所求的最少时间（单位为秒）。

样例 #1

样例输入 #1

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

样例输出 #1

66

代码求调：

#include<bits/stdc++.h>
using namespace std;
struct b
{
	int next;
	int to;
	int money;
 } ;
b e[10050];
int head[105],cnt=1,ans=0x3f3f3f3f;
typedef int LL;
inline LL read()
{
	LL x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return x*f;
}
void add(int x,int y,int z)
{
	e[cnt].money=z;
	e[cnt].to=y;
	e[cnt].next=head[x];
	head[x]=cnt++;
}
int n,m,j;
void dfs(int x,int cost,int maxx)
{
	if(cost+maxx>ans)
	{
		return ;
	}
	if(x==n)
	{
		ans=min(ans,cost+maxx);
		return ;
	}
	j=x;
	for(int i=head[x];i;i=e[i].next)
	{
		if(e[i].to==j)
		continue;
		dfs(e[i].to,cost+e[i].money,max(maxx,e[i].money));
	}
}
int main()
{
	ios::sync_with_stdio(false);
	n=read();
	m=read();
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		x=read(),y=read(),z=read(); 
		add(x,y,z);
		add(y,x,z);
	}
	j=1;
	dfs(1,0,0);
	cout<<ans;
}