洛谷 [P2349] 金字塔

洛谷【P2349】金字塔

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

输入输出格式

输入格式：

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

输出格式：

输出所求的最少时间（单位为秒）。本题需要统计每条到达终点的路径，并在其中求出最大的一条边

解题

最后统计答案的时候只需要当前路径的长度+其中最大的一条边

公式：ans=max⁡{dis[x]+maxedge[x]}ans= \max \{ dis[x]+maxedge[x]\}

但我要介绍一个新的算法，此题可用A*来做

A*的大体思路是这样的：

我们构造需要一个估价函数来寻找最优解
初始化出每个结点的预估值(这道题预估值为每个结点到终点的最短路径长度，可用反向最短路求)
每次扩展最优的结点(因此可以用堆来维护，我用的是STL优先队列)
每次扩展每个结点的实际值(这到题的实际值为当前结点到起点的路径长度)
最后每次到达终点时我们统计答案

运行速度还是可以，相比二分+dijkstra快很多

看到别人还可以之用一次spfa就可以跑实在是dalao先%%%

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <queue>

using namespace std;
const int maxn=100+5;
const int maxm=2000+5;
struct e{
    int to,nxt,w;
};
e edge[maxm<<1];
int head[maxn],edge_len,n,m;
int dis[maxn],ans=0x3f3f3f3f;
struct nd{
    int node,len,maxx;
    bool operator <(const nd &a)const{
        return len+dis[node]>a.len+dis[a.node];
    }
};

inline void edge_add(int u,int v,int w)
{
    edge[edge_len].to=v;
    edge[edge_len].w=w;
    edge[edge_len].nxt=head[u];
    head[u]=edge_len++;
}

inline int inint() //快读
{
    int x=0;char c=getchar();bool flag=false;
    for(;!isdigit(c);c=getchar()) if(c=='-') flag=true;
    for(;isdigit(c);x=x*10+c-'0',c=getchar());
    return flag?-x:x;
}

bool inq[maxn];
void spfa(int s) //反向跑最短路
{
    queue<int> q;
    q.push(s);
    inq[s]=true,dis[s]=0;
    while(!q.empty())
    {
        int now=q.front();q.pop();
        inq[now]=false;
        for(int i=head[now],v=edge[i].to;~i;i=edge[i].nxt,v=edge[i].to)
        {
            if(dis[v]>dis[now]+edge[i].w)
            {
                dis[v]=dis[now]+edge[i].w;
                if(!inq[v]) inq[v]=true,q.push(v);
            }
        }
    }
}

void Astar(int s,int t) //A*统计到目标路径的最小值
{
    priority_queue<nd> q;
    nd temp;
    temp.len=0,temp.node=s,temp.maxx=0;
    q.push(temp);
    while(!q.empty())
    {
        nd now=q.top();q.pop();
        if(now.node==t)
        {
            ans=min(ans,now.len+now.maxx);  //更新答案
            continue;
        }
        for(int i=head[now.node],v=edge[i].to;~i;i=edge[i].nxt,v=edge[i].to)
        {
            temp=now;
            temp.len+=edge[i].w;
            temp.node=v;
            temp.maxx=max(temp.maxx,edge[i].w);
            if(temp.len+temp.maxx+dis[v]>ans) continue; //如果当前大于最优解则跳出
            q.push(temp);
        }
    }
}

int main(int argc, char **argv)
{
    memset(head,-1,sizeof(head));
    memset(dis,0x3f3f3f3f,sizeof(dis));
    n=inint(),m=inint();
    for(int i=1;i<=m;i++)
    {
        int a=inint(),b=inint(),c=inint();
        edge_add(a,b,c),edge_add(b,a,c);
    }
    spfa(n);
    Astar(1,n);
    printf("%d\n",ans);
    return 0;
}