Codeforces 938D. Buy a Ticket (最短路+建图)

题目大意：

有n座城市，每一个城市都有一个听演唱会的价格，这n座城市由m条无向边连接，每天变都有其对应的边权。现在要求出每个城市的人，看一场演唱会的最小价值(总共花费的价值=所看演唱会的价值+该城市的人去那个城市看演唱会的往返距离之和)。

解题分析：
比较好的一道最短路题，主要考察建图能力。我们不妨建立一个虚拟源点，然后该源点向所有的边都连上一条无向边，边权为对应点的点权。然后所有的点之间通过m条边连接，只不过边权设为2倍原边权。最后就是从源点跑一遍最短路，就能得到每个城市的人能够看演唱会的最小价值。这里有点逆向思维的意思，源点向所有点连一条边权为$a[i]$的边，代表该点作为最后看演唱会的城市，所贡献的价值。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5+ ;

const ll INF = 1e18;

template<typename T>

inline void read(T&x){

    x=;int f=;char c=getchar();

    while(c<'' || c>''){ if(c=='-')f=-;c=getchar(); }

    while(c>='' && c<=''){ x=x*+c-'';c=getchar(); }

    x*=f;

}

struct Edge{ int from,to,nxt;ll val; }e[N<<];

int n,m,cnt;

int head[N],vis[N];

struct Node{

    int loc;ll dist;

    bool operator < (const Node &tmp)const{ return dist>tmp.dist; }

}node[N];

inline void add(int u,int v,ll w){

    e[++cnt]=(Edge){u,v,head[u],w};

    head[u]=cnt;

}

inline void Dij(int st){

    for(int i=;i<=n;i++){

        vis[i]=,node[i]=(Node){i,INF};

    }

    priority_queue<Node>q;

    node[].dist=;

    q.push(node[]);

    while(q.size()){

        int u=q.top().loc;q.pop();

        if(vis[u])continue;

        vis[u]=;

        for(int i=head[u];i;i=e[i].nxt){

            int v=e[i].to;ll cost=e[i].val;

            if(node[v].dist>node[u].dist+cost){

                node[v].dist=node[u].dist+cost;

                q.push(node[v]);

            }

        }

    }

}

int main(){

    read(n);read(m);

    for(int i=;i<=m;i++){

        int u,v;ll w;

        read(u);read(v);read(w);

        add(u,v,*w);add(v,u,*w);

    }

    for(int i=;i<=n;i++){

        ll val;read(val);

        add(,i,val);add(i,,val);

    }

    Dij();

    for(int i=;i<=n;i++)

        i==n?printf("%lld\n",node[i].dist):printf("%lld ",node[i].dist);

}

巴特西

Codeforces 938D. Buy a Ticket (最短路+建图)

最新文章

热门文章