PTA天梯赛L2题解集

前言

在刷L2的过程中，深感基础之薄弱，特写此博客总结。

L2-001紧急救援

题意：求最短路径的条数，在最短的路径中找出一条结点合最大的，并且输出路径。

#include <bits/stdc++.h>

using namespace std;
const int maxn=505;
const int maxm=250000+5;
const int INF=0x3f3f3f3f;
struct E
{
    int to,w,next;
} edge[maxm];

int head[maxn],vis[maxn],d[maxn],sum[maxn],num[maxn],path[maxn],o[maxn];
int n,m,S,D;
int tot=1;
void AddEdge(int u,int v,int w)
{
    edge[tot].w=w;
    edge[tot].to=v;
    edge[tot].next=head[u];
    head[u]=tot++;
}

priority_queue<pair<int,int> > q;

void dijikstra()
{

    for(int i=0; i<=n; i++) d[i]=INF,vis[i]=0;
    d[S]=0;
    sum[S]=1;

    q.push(make_pair(0,S));
    while(q.size())
    {
        int x=q.top().second;
        q.pop();
        if(vis[x]) continue;
        vis[x]=1;

        for(int i=head[x]; i; i=edge[i].next)
        {
            int v=edge[i].to,w=edge[i].w;
            if(d[v]>d[x]+w)
            {
                d[v]=d[x]+w;
                sum[v]=sum[x];
                num[v]=num[x]+o[v];
                path[v]=x;
                q.push(make_pair(-d[v],v)); //填入负数,因为优先队列默认排大的数
            }
            else if(d[v]==d[x]+w){
                sum[v]+=sum[x];
                if(num[v]<num[x]+o[v]){
                    num[v]=num[x]+o[v];
                    path[v]=x;
                }

            }

        }

    }

}
int c[maxn];
void print(){

    int pre=path[D];
    int tot=0;
    while(pre!=-1){
        c[tot++]=pre;
        pre=path[pre];
    }
    while(tot--){
        cout<<c[tot]<<" ";
    }
    cout<<D;
}
int main()
{
    cin>>n>>m>>S>>D;
    path[S]=-1;
    for(int i=0;i<n;i++) cin>>num[i],o[i]=num[i];
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        AddEdge(u,v,w);
        AddEdge(v,u,w);
    }
    dijikstra();
    printf("%d %d\n",sum[D],num[D]);
    print();

    return 0;
}

PTA天梯赛L2题解集

原文：https://www.cnblogs.com/sober666/p/13939514.html