题解：AT_past202107_k 急ぎ旅

题目传送门

图论中的最短路板子题。

题目大意

给出一个无向图，求点 1 到点 n 的最短路经过点的最大点权和。

注意这里是先求最短路，然后在所有最短路中选一个最大点权和。

代码

直接展示代码，所有要注意的细节以及问题都体现在注释中。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define Pair pair<int,int>
ll n,m,a[200005];//含义如题目所示 
ll tot=0,h[200005];//以链表实现的邻接表 
bool f[200005];//标记数组 
ll d[200005],ans[200005];//d[i]表示从起点到i的最短路径，ans[i]表示从起点到这个点的最大数字之和 
struct abc{
    ll to,nxt,w;
}lb[500005];
void add(int x,int y,int z){
    tot++;
    lb[tot].to=y;
    lb[tot].w=z;
    lb[tot].nxt=h[x];
    h[x]=tot;
}
void bfs(int x){
    priority_queue< Pair >q;
    q.push(make_pair(0,x));//运用pair的优先队列，pair.first存储路径长度，pair.second存储这个点 
    ans[x]=a[x]; 
    f[x]=1;
    d[x]=0;//初始化，具体含义请看上文 
    while(!q.empty()){
        Pair ud=q.top();
        q.pop();
        int u=ud.second;
        f[u]=0;
        for(int i=h[u];i;i=lb[i].nxt){
            int v=lb[i].to,w=lb[i].w;
            if(d[v]>d[u]+w){//三角优化 
                d[v]=d[u]+w;
                ans[v]=ans[u]+a[v];//注意加上本身的值 
                if(f[v]) continue;
                q.push(make_pair(-d[v],v));//因为优先队列实现的是最大堆，并且以第一关键词排序，只要使用时加个负号就能使成为小根堆
                f[v]=1;
            }
            else if(d[v]==d[u]+w&&ans[u]+a[v]>ans[v]) ans[v]=ans[u]+a[v];//如果有多条路径相同，更新最大点权和
        }
    }//Dijkstra模板 
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);//注意无向图！！！ 
    }
    for(int i=1;i<=n;i++) d[i]=0x7fffffffffffffff;
    bfs(1);//从起点1开始 
    cout<<ans[n];//输出在n能获得的最大数字和 
    return 0;
}