CodeForces

Buy a Ticket

题目描述

流行乐队“Flayer”宣布，他们想用一次世界巡演来作为他们的收官之作。当然，他们也将来到伯兰演出。

伯兰有 n 个城市。人们可以乘坐双向列车往返于城市之间; 一共有 m 条线路, 第 i 条线路可以从城市 vi 到城市 ui (或者从城市 ui 到城市 vi )，乘坐这条线路需要花费 wi 个硬币。

“Flayer”乐队会到访伯兰的每一个城市，第 i 个城市的音乐会门票要花费 ai 个硬币

你在伯兰的每个城市都有朋友，他们知道你编程很厉害，想让你计算出他们参观音乐会可能要花费的最少的硬币数量。对于每一个城市 i 里的朋友，你都必须计算他从城市 i 前往某个城市 j (或者可能停留在城市 i)，参加那里的音乐会，然后返回城市 i (如果 j ≠ i) 所花费的最少硬币数量。

严格来说，对于每一个城市 , d(i, j) 就是你从一个城市 i 到另一个城市 j 所花费的最少的硬币数。如果没有办法从一个城市 i 到另一个城市 j，那么我们认为 d(i, j) 是无限大的。

输入

第一行包含两个整数 n 和 m (2 ≤ n ≤ 2·105, 1 ≤ m ≤ 2·105).

接下来有 m 行输入，每一行包含 3 个整数 vi ，ui 和 wi (1 ≤ vi ，ui ≤ n ，vi ≠ ui ，1 ≤ wi ≤ 1012) ，表示第 i 条列车路线连接的城市 vi 和城市 ui 以及乘坐列车的车票费用 wi。没有任何的火车线路连接同一对城市，也就是说，如果输入中已经有一对城市 (v ，u)，之后的输入中既没有 (v ，u) 也没有 (u ，v) 。

最后一行包含 n 个整数 a1 ，a2, ... ak (1 ≤ ai ≤ 1012) — 代表城市 i 的演唱会票价。

输出

打印 n 个整数。第 i 个数就是一个人从城市 i 前往城市 j (或可能停留在城市 i ), 参加那里的音乐会并返回城市 i (如果 j ≠ i ) 所花费的硬币的最小数量。

样例

输入

输出

6 14 1 25

输入

输出

12 10 12

分析

首先想到的肯定是暴力，从每一个点开始跑最短路，最后再分别输出结果，但是这样复杂度肯定吃不消

题目中也没有说给出的是一棵树，所以树形DP也不太可行

所以我们考虑建边时做一些处理

我们建一个超级源点跑最短路，和昂贵的聘礼那一道题有点像

对于边权，我们把它乘2再正常建边，因为我们要往返各一次

对于点权，我们从超级源点向该点建一条边，边权为点权，代表在某一个点停留所花费的时间

最后再从超级源点开始跑一个最短路就可以了

不要忘了开long long

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
typedef long long ll;
struct asd{
    ll from,to,next,val;
}b[maxn];
int head[maxn],tot=1;
void ad(ll aa,ll bb,ll cc){
    b[tot].from=aa;
    b[tot].to=bb;
    b[tot].val=cc;
    b[tot].next=head[aa];
    head[aa]=tot++;
}
struct jie{
    ll num,dis;
    jie(ll aa=0,ll bb=0){
        num=aa,dis=bb;
    }
    bool operator < (const jie& A) const{
        return dis>A.dis;
    }
};
priority_queue<jie> q;
ll dis[maxn];
bool vis[maxn];
void DIJ(){
    memset(dis,0x3f,sizeof(dis));
    dis[0]=0;
    q.push(jie(0,0));
    while(!q.empty()){
        int now=q.top().num;
        q.pop();
        if(vis[now]) continue;
        vis[now]=1;
        for(ll i=head[now];i!=-1;i=b[i].next){
            ll u=b[i].to;
            if(dis[u]>dis[now]+b[i].val){
                dis[u]=dis[now]+b[i].val;
                q.push(jie(u,dis[u]));
            }
        }
    }
}
int main(){
    memset(head,-1,sizeof(head));
    ll n,m;
    scanf("%lld%lld",&n,&m);
    for(ll i=1;i<=m;i++){
        ll aa,bb,cc;
        scanf("%lld%lld%lld",&aa,&bb,&cc);
        ad(aa,bb,cc*2ll);
        ad(bb,aa,cc*2ll);
    }
    for(ll i=1;i<=n;i++){
        ll aa;
        scanf("%lld",&aa);
        ad(0,i,aa);
    }
    DIJ();
    printf("%lld",dis[1]);
    for(ll i=2;i<=n;i++){
        printf(" %lld",dis[i]);
    }
    printf("
");
    return 0;
}