题解 P2349 【金字塔】
大头冲锋车丶
·
·
题解
我们用 dijkstra 来写。
与平常 dijkstra 不同的是，此题还需要维护该条路上最大权值，故我们可以用一个pre[i] 数组维护最优解这条路上的最大权值。
因为有些路它不加两倍权值的话会导致比正确答案更短，这样记录就错了。
其次，像上面所说的，我们在放缩的时候，不应该用 $dist[]$ 直接存储我们需要的答案，即先不再加上最大权值。
所以我们最短路跑的应该是:
1、在真正意义上的最短路值却先没有再加上这条路最长权值的 $dist[i]$ 。
2、$pre[i]$ 始终保存的是，每次放缩后的真正意义的最短路上，最长路权值。
故我们最后输出 $dist[n] + pre[n]$ 即可。
**此外注意的是：我们不需要用 $vis[]$ 标记已走过或已经处理最短路答案，然后不再更新。** 这将会导致答案出错，因为可能从已经处理过的 $u$ 点 走到已经处理过的 $v$ 点，且更新到 $v$ 点的最短路。
比如样例中：根据优先队列顺序，到最后，会先更新节点 ⑦ ，再更新节点 ④，而如果标记 $vis[7]=true$ 的话，那么会导致 ④ --> ⑦ 这条路不再贡献于 $dist[7]$ ，导致答案出错。
**代码如下：**
```cpp
#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
#define maxn 108
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
int n,m,cnt;
int head[maxn];
ll pre[maxn],dist[maxn];
bool vis[maxn];
struct Node
{
int to;
ll val;
Node (){};
Node(ll _val,int _to){
to=_to,val=_val;
}
bool operator < (const Node &a) const{
return val>a.val;
}
};
struct Edge
{
int to;
ll val;
int next;
}edge[2008<<1];
inline void add(int u,int v,ll w)
{
edge[++cnt].to=v;
edge[cnt].val=w;
edge[cnt].next=head[u];
head[u]=cnt;
return;
}
void dijkstra(int u)
{
priority_queue<Node> q;
while(!q.empty()) q.pop();
for(int i=1;i<=n;i++) {dist[i]=inf,vis[i]=false;pre[i]=0;}
dist[u]=0;
q.push(Node(0,1));
while(!q.empty())
{
int u=q.top().to;
ll t=dist[u];
q.pop();
for(int i=head[u];i;i=edge[i].next){
int v=edge[i].to;
if((dist[v]+pre[v]>t+edge[i].val+max(edge[i].val,pre[u]))){
pre[v]=max(pre[u],edge[i].val);
dist[v]=edge[i].val+t;
q.push(Node(dist[v],v));
}
}
}
return;
}
int main()
{
//freopen("test.in","r",stdin);
scanf("%d%d",&n,&m);
int A,B;
ll C;
for(int i=1;i<=m;i++){
scanf("%d%d%lld",&A,&B,&C);
add(A,B,C);add(B,A,C);
}
dijkstra(1);
printf("%lld\n",dist[n]+pre[n] );
}
```