【最短路】CF 938D Buy a Ticket

题目大意

流行乐队“Flayer”将在\(n\)个城市开演唱会，这\(n\)个城市的人都想去听演唱会，每个城市的票价不同，于是这些人就想是否能去其他城市听演唱会更便宜，但是去其他的城市也需要路费。

输入格式

第一行包含两个整数\(n\)和\(m\)。
接下来\(m\)行，每行三个数\(u、v、w\)表示\(u\)城市到\(v\)城市要\(w\)元。
接下来\(n\)个数，表示每个城市的票价\(a\)。

输出格式

输出n个数字，表示对应的人到别的城市参加演唱会再返程的最小费用，当然也可以选择在自己的城市参加演唱会

数据范围

\(2≤n≤2·10^5,1≤m≤2·10^5,1≤w_i≤10^{12},1≤a_i≤10^{12}\)

样例

4 2
1 2 4
2 3 7
6 20 1 25

样例输出

6 14 1 25

思路

新建一个点\(P\)，向每个城市连一条长度为该城市票价的边。这样从\(P\rightarrow u\rightarrow v\)的距离就表示从\(v\)城市买\(u\)城市的门票要花的最小费用。注意他还要返程的。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=200000+10;
const int maxm=400000+10;
int n,m;
int nxt[maxm<<1],to[maxm<<1];
ll w[maxn],dis[maxn],vis[maxn],len[maxm << 1];

struct Node{
    int u;
    ll dis;
    bool operator < (const Node &a) const{
        return dis>a.dis;
    }
};
int head[maxn],cnt;
void add(int a,int b,ll c){
    len[cnt]=c;
    to[cnt]=b;
    nxt[cnt]=head[a];
    head[a]=cnt++;
}

void Dij(int rt){
    int u=rt;
    priority_queue<Node> q;
    q.push((Node){u,0});
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
        dis[i]=1e13;//注意范围最大可能到1e12

    dis[u]=0;
    while(!q.empty()){
        u=q.top().u;q.pop();
        if(vis[u])continue;vis[u]=true;
        for(int i=head[u];i!=-1;i=nxt[i]){
            int v=to[i];
            if(dis[v]>dis[u]+len[i]){
                dis[v]=dis[u]+len[i];
                q.push((Node){v,dis[v]});
            }
        }
    }
}

int main(){
    memset(head,-1,sizeof(head));
    scanf("%d%d",&n,&m);
    for(int i=1;i <= m;i++){
        int u,v;ll l;
        scanf("%d%d%lld",&u,&v,&l);
        add(u,v,l*2);add(v,u,l*2);
    }

    for(int i=1;i<=n;i++){
        scanf("%lld",&w[i]);
        add(0,i,w[i]);
    }

    Dij(0);

    for(int i=1;i<=n;i++)
        printf("%lld ",dis[i]);

    return 0;
}