【最短路】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;
}